Cod sursa(job #702390)

Utilizator wamfeverDobos Ionut wamfever Data 1 martie 2012 21:30:38
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
#include<algorithm>
using namespace std;

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

int n, maxx, pwxx;
int v[100001], T[100001], scm[100001];

void afis(int k)
{
    if( T[k] ) afis( T[k] );
    g << v[k] << " ";
}

int main()
{
    f >> n;
    for(int i=1; i<=n; i++)
        f >> v[i];
    int max;
    for(int i=1; i<=n; i++)
    {
        max = 0;

        for(int j=i-1; j; j--)
            if( v[i] > v[j] && max < scm[j] )
                max = scm[j], T[i] = j;

        scm[i] = max + 1;
        if(maxx < scm[i])
            maxx = scm[i], pwxx = i;
    }

    g << maxx << "\n";

    afis(pwxx); g << "\n";
    return 0;
}