Cod sursa(job #1802922)

Utilizator ancabdBadiu Anca ancabd Data 10 noiembrie 2016 19:47:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>

using namespace std;

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

#define MAX 100000
int a[MAX + 1], l[MAX + 1], bef[MAX + 1], n, lmax, ind, rez[MAX + 1];

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> a[i];
        for (int j = 1; j <= i; j++)
            if (a[j] < a[i] && l[j] + 1 > l[i])
            {
                l[i] = l[j] + 1;
                bef[i] = j;
            }
        if (l[i] > lmax)lmax = l[i], ind = i;
    }
    fout << lmax + 1 << '\n';
    while (a[ind] != 0)
    {
        rez[++rez[0]] = a[ind];
        ind = bef[ind];
    }
    for (int i = rez[0]; i>=1; i--)fout << rez[i] << ' ';
    return 0;
}