Cod sursa(job #384529)

Utilizator Adela_BaciuAdela Baciu Adela_Baciu Data 20 ianuarie 2010 12:32:40
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<cstdio>
int n,i,j,max,poz,a[100010],sol[100010],lung[100010],pred[100010];
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	lung[1]=1;
	for(i=2;i<=n;i++)
	{
		lung[i]=0;
		for(j=1;j<i;++j)
			if(lung[j]>lung[i]&&a[i]>a[j])
			{
				lung[i]=lung[j];
				pred[i]=j;
			}
		lung[i]++;
		
	}
	max=0;
	poz=0;
	for(i=1;i<=n;i++)
		if(max<lung[i])
		{
			max=lung[i];
			poz=i;
		}
	printf("%d\n",max);
	sol[0]=0;
	while(poz!=0)
	{
		sol[++sol[0]]=a[poz];
		poz=pred[poz];
	}
	for(i=sol[0];i>=1;i--)
		printf("%d ",sol[i]);
	return 0;
}