Cod sursa(job #1334980)

Utilizator greenday28stoienescu paul greenday28 Data 4 februarie 2015 20:37:21
Problema Subsir crescator maximal Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<fstream>
#include<algorithm>
using namespace std;
int main()
{
    ifstream in("scmax.in");
    ofstream out("scmax.out");
    int n,i,poz,lmax,j,l[100002],next[100002],x[100002];
    in>>n;
    for(i=1;i<=n;i++)
    in>>x[i];
    l[n]=1;
    next[n]=1;
    for(i=n-1;i>=1;i--)
    {
        l[i]=1;
        next[i]=0;
        for(j=i+1;j<=n;j++)
            if(x[j]>x[i])
                if(l[i]<l[j]+1)
                {
                    l[i]=l[j]+1;
                    next[i]=j;
                }
    }
    lmax=l[1];
    poz=1;
    for(i=2;i<=n;i++)
        if(l[i]>lmax)
        {
            lmax=l[i];
            poz=i;
        }
        out<<lmax<<endl;
        while(poz>1)
        {
            out<<x[poz]<<" ";
            poz=next[poz];
        }
}