Cod sursa(job #1263217)

Utilizator lucian.okapiNestian Lucian-Dan lucian.okapi Data 14 noiembrie 2014 09:30:36
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>

using namespace std;

long a[100009],lis[100009],next[100009];

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

int main()
{
    int n,i,poz,j,maxim=0;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    lis[n]=1;
    next[n]=n+1;
    for(i=n-1;i>=1;i--)
    {
        maxim=0;poz=n-1;
        for(j=i+1;j<=n;j++)
            if(a[i]<a[j] && maxim<lis[j])
        {
            maxim=lis[j];
            poz=j;
        }
        lis[i]=1+maxim;
        next[i]=poz;
    }
    maxim=lis[1];poz=1;
    for(i=2;i<=n;i++)
        if(maxim<lis[i])
    {
        maxim=lis[i];
        poz=i;
    }
    fout<<maxim<<"\n";
    while(poz!=n+1)
    {
        fout<<a[poz]<<" ";
        poz=next[poz];
    }


    return 0;
}