Cod sursa(job #895803)

Utilizator StefanOnuOnutu Codrin Stefan StefanOnu Data 27 februarie 2013 12:36:41
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>

using namespace std;

ifstream in("scmax.in");
ofstream out("scmax.out");
long a[100000],lg[100000],urm[100000],n,i,x,lgm,jm,j;

int main()
{
    in>>n;
    for(i=1;i<=n;i++)
        in>>a[i];
    lg[n]=1;
    urm[n]=0;
    for(i=n-1;i>0;i--)
    {
        lgm=0;
        jm=0;
        for(j=i+1;j<=n;j++)
            if(a[i]<a[j]&&lg[j]>lgm) {jm=j;lgm=lg[j];}
        lg[i]=lgm+1;
        urm[i]=jm;
    }
    lgm=0;
    x=0;
    for(i=1;i<=n;i++)
        if(lgm<lg[i]) {lgm=lg[i];x=i;}
    out<<lgm<<endl<<a[x]<<' ';
    while(urm[x])
    {
        out<<a[urm[x]]<<' ';
        x=urm[x];
    }
    return 0;
}