Cod sursa(job #866735)

Utilizator thewildnathNathan Wildenberg thewildnath Data 28 ianuarie 2013 18:13:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<stdio.h>
int v[100010],best[100010],t[100010];
void afisare(int poz)
{
	if(t[poz]==0)
	{
		printf("%d ",v[poz]);
		return ;
	}
	afisare(t[poz]);
	printf("%d ",v[poz]);
}
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	int n,i,j,max=0,poz;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	
	for(i=1;i<=n;i++)
	{
		best[i]=1;
		for(j=i-1;j>=1;j--)
			if(v[j]<v[i]&&best[j]>=best[i])
			{
				best[i]=best[j]+1;
				t[i]=j;
			}
		if(best[i]>max)
		{
			poz=i;
			max=best[i];
		}
	}
	printf("%d\n",max);
	afisare(poz);
	printf("\n");
	return 0;
}