Cod sursa(job #829053)

Utilizator TheNechizFMI Razvan Birisan TheNechiz Data 4 decembrie 2012 20:38:34
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
# include <fstream>

using namespace std;

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

const int dim = 100001;
int v[dim],lgm[dim];

int main()
{
    int n,i,k,t,max;

    fin >> n;
    for( i = 1 ; i <= n ; ++i )
        fin >> v[i];
    lgm[n] = 1;

    for( k = n - 1 ; k >= 1 ; --k )
    {
        max = 0;
        for( i = k + 1 ; i <= n ; ++i )
            if( v[i] >= v[k] && lgm[i] > max )
                max = lgm[i];
        lgm[k] = max + 1;
    }

    max = lgm[1];
    t = 1;
    for( k = t+1 ; k <= n ; ++k )
        if( lgm[k] > max )
        {
            max = lgm[k];
            t = k;
        }

    fout << max << '\n';
    for( i = t + 1 ; i <= n ; ++i )
        if( v[i] > v[t] && lgm[i] == max - 1 ){
            fout << v[i] << " ";
            max = max - 1;
        }

    return 0;
}