Cod sursa(job #409977)

Utilizator AnDrEwBoYA Andrei AnDrEwBoY Data 3 martie 2010 22:57:26
Problema Subsir crescator maximal Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<cstdio>
#define MAX_N 100000+1
int i,n,k,MAX,MAXS,st,L[MAX_N],a[MAX_N];
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
}
void solve()
{
	L[n]=1;
	for(k=n-1;k>=1;k--)
	{
		for(i=k+1;i<=n;i++)
			if(a[i]>a[k] && L[i]>MAX)
				MAX=L[i];
		L[k]=1+MAX;
		if(L[k]>MAXS)
		{
			MAXS=L[k];
			st=k;
		}
	}
	printf("%d\n%d ",MAXS,a[st]);
	for(i=st+1,k=st;k<st+L[st];i++)
		if(a[i]>a[k]) printf("%d ",a[i]),k=i;
}