Cod sursa(job #899795)

Utilizator alexu128Rosu Alexandru alexu128 Data 28 februarie 2013 16:25:16
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 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)
			{
				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];
	}
}