Cod sursa(job #539004)

Utilizator daniel.florinPitis Daniel-Florin daniel.florin Data 22 februarie 2011 10:35:31
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <cstdio>

long long a[100001],l[100001],poz[100001];

int main()
{
	long long i,n,j,max,pozmax;
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%lld",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]);
	}
	l[n]=1; poz[n]=-1;
	for(i=n-1;i>0;--i)
		for(l[i]=1, poz[i]=-1, j=i+1; j<=n; ++j)
			if(a[i]<=a[j] && l[i]<1+l[j])
				{ l[i]=1+l[j]; poz[i]=j; }
	max=l[1], pozmax=1;
    for(i=2;i<=n;++i)
		if(max<l[i]) { max=l[i]; pozmax=i; }
	printf("%lld\n",max);
	for(i=pozmax; i!=-1; i=poz[i]) printf("%lld ",a[i]);
	return 0;
}