Cod sursa(job #637903)

Utilizator d.andreiDiaconeasa Andrei d.andrei Data 20 noiembrie 2011 17:27:55
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <cstdio>

#define file_in "scmax.in"
#define file_out "scmax.out"

int N,V[101000],i,best[100100],poz[101000],j,max,p;

int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &N);
	for (i=1;i<=N;++i)
		 scanf("%d", &V[i]);
	
	best[N]=1;
	poz[N]=-1;
	for (i=N-1;i>=1;--i){
		best[i]=1;
		poz[i]=-1;
		for (j=i+1;j<=N;++j)
			 if (V[i]<V[j] && best[i]<best[j]+1){
				 best[i]=best[j]+1;
				 poz[i]=j;
				 //p=i;
				 if (best[i]>max)
					 max=best[i],p=i;
			 }
	}
	
	printf("%d\n", max);
	i=p;
	while(i!=-1){
		printf("%d ", V[i]);
		i=poz[i];
	}
	
	return 0;
	
}