Cod sursa(job #408930)

Utilizator palcuiealexAlex Palcuie palcuiealex Data 3 martie 2010 12:44:48
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include <cstdio>

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

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

int main()
{
	freopen("date.in","r",stdin);
	
	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;
}