Cod sursa(job #427408)

Utilizator miticaMitica mitica Data 27 martie 2010 20:42:59
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
# include <stdio.h>
# define nmax 100005

long n,a[nmax],l[nmax],p[nmax],i,j,x;

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