Cod sursa(job #707643)

Utilizator gabrielvGabriel Vanca gabrielv Data 5 martie 2012 21:58:36
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
using namespace std;
#include<cstdio>
#define MAX 100005
int v[MAX],best[MAX],pred[MAX],rezultat[MAX];
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	int n,i,ant,j,k,maxbest,baux;
	scanf("%d",&n);
	best[1]=1; ant=v[1]; pred[1]=0; best[0]=-1;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&v[i]);
		
		baux=0;
		for(j=1;j<i;j++)
			if((best[j]>best[baux])&&(v[j]<v[i]))
				baux=j;
		if(baux)
		{
			best[i]=best[baux]+1;
			pred[i]=baux;
		}
		else
		{
			best[i]=1;
			pred[i]=0;
		}
	}
	for(maxbest=0,i=1;i<=n;i++)
		if(best[i]>best[maxbest])
			maxbest=i;
	k=best[maxbest];
	printf("%d\n",best[maxbest]);
	rezultat[k--]=v[maxbest]; 
	for(i=maxbest;pred[i];i=pred[i])
		//if(pred[i]!=-1)
			rezultat[k--]=v[pred[i]];	
	for(i=1;i<=best[maxbest];i++)
		printf("%d ",rezultat[i]);
	printf("\n");
	return 0;
}