Cod sursa(job #403805)

Utilizator andreirRoti Andrei andreir Data 25 februarie 2010 12:35:40
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<cstdio>
#define lgmax 100001
using namespace std;
int n,v[lgmax],i,k,L[lgmax],mx,max,t;
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("max=%d\n",max);
	
	printf("%d ",v[t]);
	for(i=t+1;i<=n;i++)
		if ( (v[i]>=v[t]) && (L[i]==max-1) )
		{
			printf("%d ",v[i]);
			max--;
		}
	
	return 0;
}