Cod sursa(job #1649266)

Utilizator crysstyanIacob Paul Cristian crysstyan Data 11 martie 2016 13:03:12
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <algorithm>
#define NMAX 100005

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int i, n, j, dp[NMAX], tata[NMAX], v[NMAX], best = -1, start;

int main()
{
    f >> n;

    for (i = 1; i <= n; ++ i)
        f >> v[i];

    dp[n] = 1;

    for (i = n - 1; i >= 1; -- i)
    {
        dp[i] = 1;

        for (j = i + 1; j <= n; ++ j)
            if (v[i] < v[j] && dp[i] < dp[j] + 1)
        {
            dp[i] = dp[j] + 1;
            tata[i] = j;
        }

        if (dp[i] > best)
        {
            best = dp[i];
            start = i;
        }
    }

    g << best << '\n';

    while (start != 0)
    {
        g << v[start] << " ";
        start = tata[start];
    }
    return 0;
}