Cod sursa(job #899821)

Utilizator alexu128Rosu Alexandru alexu128 Data 28 februarie 2013 16:32:39
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <cstdio>
using namespace std;
int main()
{
	int lung[100000],next[100000],n,i,j,max,maxtot=0,pozt;
	long long v[100000];
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%lld",&v[i]);
	lung[n-1]=1;
	next[n-1]=-1;
	for(i=n-2;i>=0;i--)
	{
		max=0;
		for(j=i+1;j<n;j++)
			if((v[j]>v[i]) && (lung[j]>max || (lung[j]==max && v[j]>next[i])))
			{
				max=lung[j]+1;
				next[i]=j;
			}
		lung[i]=max;
		if(max>maxtot)
		{
			pozt=i;
			maxtot=max;
		}
	}
	printf("%d \n",maxtot);
	while(lung[pozt])
	{
		printf("%lld ",v[pozt]);
		pozt=next[pozt];
	}
}