Cod sursa(job #828480)

Utilizator RaduDoStochitoiu Radu RaduDo Data 3 decembrie 2012 20:26:32
Problema Subsir crescator maximal Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<cstdio>
#define maxn 100005
using namespace std;
int L[maxn],urm[maxn],a[maxn],i,n,j,maxi,p,p2,maxt;

int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%d",&a[i]);
	L[n]=1;
	urm[n]=-1;
	for(i=n-1;i>=1;--i)
	{
		maxi=1;
		urm[i]=-1;
		for(j=i+1;j<=n;++j)
			if(a[i]<a[j]&&L[j]+1>maxi)
				maxi=L[j]+1,p=j;
		L[i]=maxi;
		urm[i]=p;
		if(L[i]>maxt)
			maxt=L[i],p2=i;
	}
	printf("%d\n",L[p2]);
	for(i=p2; i!=-1; i=urm[i])
		printf("%d ",a[i]);
	printf("\n");
	return 0;
}