Cod sursa(job #884290)

Utilizator ancutza96Anca Grigoriu ancutza96 Data 20 februarie 2013 20:41:45
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream.h>
int a[100001]={0},lg[100001]={0},urm[100001]={0},lgm,n,i,j,jm=0,im=0,nr=0;
int main ()
{
    ifstream fin("scmax.in");
	ofstream fout("scmax.out"); 	
	fin>>n;
    for (i=1;i<=n;i++) fin>>a[i];
	lg[n]=1;
    urm[n]=0;
    for (i=n-1;i>=1;i--)
    {
        lgm=0;
        jm=0;

        for (j=i+1;j<=n;j++)
            if(a[i]<=a[j]&& lg[j]>lgm)
            {
                lgm=lg[j];
                jm=j;
            }

        lg[i]=lgm+1;
        urm[i]=jm;
    }

    lgm=0;
    for (i=1;i<=n;i++)
        if(lgm<lg[i]) {lgm=lg[i]; im=i;}

    nr=0;
    i=im;
    do{
        nr++;
        i=urm[i];
    }while(i>0);
    fout<<nr<<'\n';
    do{
        fout<<a[im]<<' ';
        im=urm[im];
    }while(im>0);
    return 0;
}