Cod sursa(job #1651044)

Utilizator ioan.veveraIoan Vevera ioan.vevera Data 11 martie 2016 23:53:12
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>

using namespace std;
ifstream fin ("scmax.in");
ofstream fout("scmax.out");
long n,v[100001],l[100001],mx,mxi,sol[100001],k,auxi;
int main()
{
    fin>>n;
    for(int i=1; i<=n; i++) fin>>v[i];
    for(int i=1; i<=n; i++)
    {
        l[i]=1;
        for(int j=1; j<i; j++) if(v[j]<v[i] && l[j]+1>l[i]) l[i]=l[j]+1;
    }
    for(int i=1; i<=n; i++) if(l[i]>mx) mx=l[i],mxi=i;
    fout<<mx<<'\n';
    int ok;auxi=mxi;
    for(int i=mx-1; i>=1; i--)
    {
        ok=0;
        for(int j=mxi; !ok && j>=1; j--) if(l[j]==i && v[j]<v[mxi]) sol[++k]=v[j],ok=1,mxi=j;
    }
for(int i=k;i>=1;i--) fout<<sol[i]<<' ';fout<<v[auxi];
    return 0;
}