Cod sursa(job #408935)

Utilizator palcuiealexAlex Palcuie palcuiealex Data 3 martie 2010 12:47:18
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <cstdio>

int v[100000],a[100000],pred[100000];

int recon(int i)
{
	if(pred[i]+1) recon(pred[i]);
	printf("%d ",a[i]);
}

int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	
	int i,j,imax=0; v[0]=1; pred[0]=-1;
	
	int n; scanf("%d",&n);
	for (i=0; i<n; ++i) scanf("%d",&a[i]);
	
	for (i=1; i<n; ++i)
	{
		v[i]=1;
		pred[i]=-1;
		for (j=0; j<i; ++j)
			if ( a[j]<a[i] && v[j]+1>v[i])
			{
				v[i]=v[j]+1;
				pred[i]=j;
			}
		if (v[i]>v[imax]) imax=i;
	}
	
	printf("%d\n",v[imax]);
	recon(imax);
	
	
	return 0;
}