Cod sursa(job #409983)

Utilizator AnDrEwBoYA Andrei AnDrEwBoY Data 3 martie 2010 23:03:11
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 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--)
	{
		MAX=0;
		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;i<=n;i++)
		if (a[i]>a[st] && L[i]==MAXS-1)
			printf("%d ",a[i]),MAXS--;
}