Cod sursa(job #707976)

Utilizator valiro21Valentin Rosca valiro21 Data 6 martie 2012 10:14:07
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <cstdio>
#define NMax 10001

long n,viz[NMax],urm[NMax],v[NMax],maxit,maxt,maxx,maxi;

int main()
{
	freopen("scmax.in","rt",stdin);
	freopen("scmax.out","wt",stdout);
	
	scanf("%ld",&n);
	
	for(long i=1;i<=n;i++)
		scanf("%ld",&v[i]);
	
	viz[n]=1;
	
	for(long i=n-1;i>=1;i--)
	{
		maxx=0;
		maxi=0;
		for(long j=i+1;j<=n+1;j++)
			if(v[j]>v[i]&&viz[j]>maxx)
				maxx=viz[j],maxi=j;
			
		viz[i]=maxx+1;
		urm[i]=maxi;
		if(viz[i]>maxt)
			maxt=viz[i],maxit=i;
	}
	
	printf("%ld\n",maxt);
	
	printf("%ld ",v[maxit]);
	long x=urm[maxit];
	
	while(x)
	{
		printf("%ld ",v[x]);
		x=urm[x];
	}
	
	printf("\n");
	return 0;
}