Cod sursa(job #604652)

Utilizator ELHoriaHoria Cretescu ELHoria Data 24 iulie 2011 00:12:17
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <cstdio>

int n , a[100001] , d[100001] , last[100001] , lmax , p;

void dp()
{
	last[n] = -1 ,d[n] = 1;
	for(int i=n-1;i>=1;--i)
	{
		d[i] = 1;
		last[i] = -1;
		for(int j=i+1;j<=n;++j)
			if(a[i]<a[j] && d[i]<d[j] + 1)
			{
				d[i] = d[j] + 1;
				last[i] = j;
				if(d[i]>lmax) lmax = d[i] , p = i;
			}
	}
}

void build()
{
	while(p!=-1)
		printf("%d ",a[p]) , p = last[p];
}

int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	dp();
	printf("%d\n",lmax);
	build();
	return 0;
}