Cod sursa(job #526795)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 29 ianuarie 2011 14:39:32
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<stdio.h>

int n,i,j,lung[100001],v[100001],pred[100001],max,p;

void refac(int poz)
{
	if(pred[poz]!=0)
		refac(pred[poz]);
	printf("%d ",v[poz]);
}


int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%d",&v[i]);
	lung[1]=1; pred[1]=0;
	for(i=1;i<=n;++i)
	{
		lung[i]=0;
		for(j=1;j<i;++j)
		{
			if(v[j]>=v[i]) continue;
			if(lung[j]>lung[i])
			{
				lung[i]=lung[j];
				pred[i]=j;
			}
		}
		++lung[i];
	}
	max=0;
	for(i=1;i<=n;++i)
		if (lung[i]>max)
		{
			max=lung[i];
			p=i;
		}
	printf("%d\n",max);
	refac(p);
}