Cod sursa(job #628510)

Utilizator ContraPunctContrapunct ContraPunct Data 1 noiembrie 2011 16:49:54
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<cstdio>
#define Nmax 1001
int n;
int v[Nmax], d[Nmax];
void ReadData()
{
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
}
void Sol()
{
	int i,min,j;
	d[1]=1;
	int poz_t=1,min_t = 1;
	for(i=2;i<=n;i++)
	{
		min = 0;
		for(j=1;j<=i;j++)
			if(v[j]<v[i])
				if(d[j]>min)
				{
					min = d[j];
				}
		d[i]=min+1;
		if(d[i] > min_t)
		{
			min_t= d[i];
			poz_t=i;
		}
	}
	//return min_t;
	printf("%d\n",min_t);
	int sol[Nmax];
	int nr=1;
	sol[1]=v[min_t--];
	for(i=poz_t-1;i>=1;--i)
	{
		if(min_t == d[i])
		{
			--min_t;
			//printf("%d ",v[i]);
			sol[++nr]=v[i];
		}
	}
	for(;nr>=1;nr--)
		printf("%d ",sol[nr]);
}
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	ReadData();
	Sol();
	return 0;
}