Cod sursa(job #1961534)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 11 aprilie 2017 10:31:18
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>

using namespace std;

int a[100010], l[100010], t[100010], b[100010];

int main()
{
    ifstream fin ("scmax.in");
    ofstream fout ("scmax.out");
    int n, i, j, max, x=0;
    fin >> n;
    for (i=1; i<=n; i++)
    {
        fin >> a[i];
        max=i;
        for (j=i-1; j>=1; j--)
            if (l[j]>l[max] && a[j]<a[i])
                max=j;
        l[i]=l[max]+1;
        if (max==i)
            t[i]=0;
        else
            t[i]=max;
    }
    max=1;
    for (i=1; i<=n; i++)
    {
        if (l[i]>l[max])
            max=i;
    }
    fout << l[max] << "\n";
    while (t[max])
    {
        b[++x]=a[max];
        max=t[max];
    }
    b[++x]=a[max];
    for (i=x; i>=1; i--)
        fout << b[i] << " ";
    return 0;
}