Cod sursa(job #407150)

Utilizator BooZZySandu Bogdan BooZZy Data 2 martie 2010 09:03:30
Problema Subsir crescator maximal Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include<stdio.h>
int INF=1<<30;
int v[100005],l[100005],i,j,max,n,maxt=-1,sol[100005],k;
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	for(i=1;i<=n;i++)
	{
		max=0;
		for(j=1;j<i;j++)
			if(l[j]>max&&v[i]>v[j])max=l[j];
		l[j]=max+1;
			if(max+1>maxt)maxt=max+1;
	}
	printf("%d\n",maxt);
	for(i=n;i>=1;i--)
		if(l[i]==maxt&&v[i]<INF)
			{sol[++k]=v[i];maxt--;INF=v[i];}
	for(i=k;i>=1;i--)
		printf("%d ",sol[i]);
	return 0;
}