Cod sursa(job #899105)

Utilizator michael9ufoStanescu Mihai michael9ufo Data 28 februarie 2013 12:56:38
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int N, i, j, S[100005], D[100005], TR[100005];

int main()
{
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);

    cin>>N;

    for(i=1;i<=N;++i)
        cin>>S[i];

    D[N] = 1;
    TR[N] = N;

    for(i=N-1;i>=1;--i)
    {
        D[i] = 1;
        TR[i] = i;
        for(j=i+1;j<=N;++j)
            if(S[j] > S[i] && D[j] >= D[i])
                D[i] = D[j] + 1, TR[i] = j;

    }

    int rez=-1, st;

    for(i=1;i<=N;++i)
        if(rez < D[i])
            rez = D[i], st = i;

    cout<<rez<<"\n";
/*
    for(i=1;i<=N;++i)
        cout<<TR[i]<<" ";
        cout<<endl;
*/
    int st2 = st;

    for(i=1;i<=rez;++i)
    {
            cout<<S[st2]<<" ";
            st2 = TR[st2];
    }
    return 0;
}