Cod sursa(job #895968)

Utilizator mvcl3Marian Iacob mvcl3 Data 27 februarie 2013 13:16:17
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream>
using namespace std;

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

int n, a[100009], best[100009], pre[100009], maxim, poz;

int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i) f >> a[i];
    for(int i = n; i >= 1; --i)
    {
        best[i] = 1;
        pre[i] = -1;
        for(int j = i + 1; j <= n; ++j)
            if(a[i] < a[j] && best[i] < best[j] + 1)
            {
                best[i] = best[j] + 1;
                pre[i] = j;
                if(best[i] > maxim) maxim = best[i], poz = i;
            }
    }
    int i;
    g<<maxim<<'\n';
    for(i = poz; pre[i] != -1; i = pre[i])
        g<<a[i]<<' ';
    g<<a[i]<<'\n';

    g.close();
    return 0;
}