Cod sursa(job #333951)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 24 iulie 2009 18:04:31
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <stdio.h>
#define N 5005
int n,v[N],best[N],ant[N],rez,poz,sol[N],r;
int main()
{
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	scanf("%d",&n);
	int i,j,max;
	for (i=1; i<=n; i++)
	{
		scanf("%d",&v[i]);
		max=0;
		for (j=i-1; j>=1; j--)
			if (v[j]<v[i] && best[j]>max)
			{
				max=best[j];
				ant[i]=j;
			}
		best[i]=max+1;
		if (best[i]>rez)
		{
			rez=best[i];
			poz=i;
		}
	}
	printf("%d\n",rez);
	while (poz)
	{
		sol[++r]=poz;
		poz=ant[poz];
	}
	for (i=r; i>=1; i--)
		printf("%d ",sol[i]);
	return 0;
}