Cod sursa(job #502368)

Utilizator sabina67Zavoianu Sabina sabina67 Data 19 noiembrie 2010 09:05:30
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
const int maxn=100001;
int i,j,n,max,pmax,v[maxn],lung[maxn],pred[maxn];
void subsir(int p)
{
	if(pred[p])
		subsir(pred[p]);
	printf("%d " ,v[p]);
}

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=2;i<=n;i++)
	{
		max=0;
		pmax=0;
		for(j=1;j<i;++j)
		{
			if (v[j]>=v[i]) continue;
			if (lung[j]>max)
			{
				max=lung[j];
				pmax=j;
			}
		}
		lung[i]=1+max;
		pred[i]=pmax;
	}
	max=-1;
	pmax=0;
	for(i=1;i<=n;i++)
	{
		if(lung[i]>max) 
		{
			max=lung[i];
			pmax=i;
		}
	}
	printf( "%d\n",max);
	subsir(pmax);
	return 0;
}