Cod sursa(job #1854287)

Utilizator FrequeAlex Iordachescu Freque Data 22 ianuarie 2017 15:59:26
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

const int NMAX = 100000 + 5;

int n, maxx, x, poz;
int v[NMAX];
int dp[NMAX];
int tata[NMAX];

void Read()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
}

int main()
{
    Read();
    dp[n] = 1;
    tata[n] = -1;
    for (int i = n - 1; i >= 1; --i)
    {
        maxx = 0;
        x = -1;
        for (int j = i + 1; j <= n; ++j)
        {
            if (v[i] < v[j])
                if (dp[j] > maxx)
                {
                    maxx = dp[j];
                    x = j;
                }
        }
        dp[i] = maxx + 1;
        tata[i] = x;
    }
    maxx = dp[1];
    poz = 1;
    for (int i = 2; i <= n; ++i)
        if (maxx < dp[i])
        {
            maxx = dp[i];
            poz = i;
        }
    fout << maxx << '\n';
    while(poz != -1)
    {
        fout << v[poz] << " ";
        poz = tata[poz];
    }
}