Cod sursa(job #1088025)

Utilizator d0rina2011Craciun Dorina d0rina2011 Data 20 ianuarie 2014 08:18:10
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int v[100001],urm[100001],l[100001];
int main()
{
    int n,p,maxi=0,i,j;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    l[n]=1;
    urm[n]=0;
    for(i=n-1;i>=1;i--)
    {
        maxi=0;
        p=0;
        for(j=i+1;j<=n;j++)
            if(v[j]>v[i]&&l[j]>maxi)
                maxi=l[j],p=j;
        l[i]=maxi+1;
        urm[i]=p;
    }
    maxi=l[1];
    p=1;
    for(i=2;i<=n;i++)
        if(l[i]>maxi)maxi=l[i],p=i;
    fout<<maxi<<'\n';
    while(p>0)
    {
        fout<<v[p]<<" ";
        p=urm[p];
    }
    return 0;
}