Cod sursa(job #201715)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 3 august 2008 11:45:03
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include<stdio.h>
#define NMAX 100000

int main(){
freopen("scmax.in","r",stdin);
freopen("scmax.out","w",stdout);
int n,i,j,lmax=0,v[NMAX],l[NMAX],next[NMAX]={0},first;
scanf("%d",&n);
for(i=0;i<n;++i) scanf("%d",&v[i]);
l[n-1]=1;
for(j=n-2;j>=0;--j){
	lmax=0;
	for(i=j+1;i<n;++i)
		if(v[i]>v[j]&&l[i]>lmax) {lmax=l[i];next[j]=i;}
	l[j]=lmax+1;
	}
lmax=l[0];first=0;
for(i=1;i<n;++i) if(l[i]>lmax) {lmax=l[i];first=i;}
printf("%d\n",lmax);

i=first;
while(next[i]!=0){
	printf("%d ",v[i]);
	i=next[i];
	}
printf("%d",v[i]);
return 0;
}