Cod sursa(job #899025)

Utilizator michael9ufoStanescu Mihai michael9ufo Data 28 februarie 2013 12:37:24
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

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

    cin>>N;

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

    D[N] = 1;
    for(i=1;i<=N;++i)
        D[i] = 1;

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

    int rez = *max_element(D, D + N);

    cout<<rez<<"\n";
/*
    for(i=1;i<=N;++i)
        cout<<TR[i]<<" ";
        cout<<endl;*/
        bool fst = true;
    for(i=1;i<=N;++i)
        if(TR[i] > 0)
        {
            if(fst)
                cout<<S[i]<<" ", fst = false;

            cout<<S[TR[i]]<<" ";
            i = TR[i]-1;
            //cout<<i<<" "<<endl;
        }
    return 0;
}