Cod sursa(job #403564)

Utilizator andreirRoti Andrei andreir Data 25 februarie 2010 08:49:53
Problema Subsir crescator maximal Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<stdio.h>
#define lgmax 100001
using namespace std;

int i,n,k,mx,max,t;
int v[lgmax],L[lgmax];

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]);
	
	L[n]=1;
	for(k=n-1;k>=1;k--)
	{
		mx=0;
		for(i=k+1;i<=n;i++)
			if(v[k]<v[i] && L[i]>mx)
				mx=L[i];
		L[k]=mx+1;
		if(L[k]>max)
		{
			max=L[k];
			t=k;
		}
	}
	printf("%d\n",max);
	
	
	printf("%d ",v[t]);
	for(i=t+1;i<=n;i++)
		if(v[i]>v[t])
		{
			printf("%d ",v[i]);
			t=i;
			max--;
		}
		
	return 0;
}