Cod sursa(job #412408)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 5 martie 2010 16:35:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <cstdio>
#include <cstring>

#define file_in "scmax.in"
#define file_out "scmax.out"

#define Nmax 123213

int n,v[Nmax],i,j,best[Nmax],poz[Nmax],max,p;

void scrie()
{
	i=p;
	while(i!=-1)
	{
		printf("%d ", v[i]);
		i=poz[i];
	}
}


int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
	for (i=1;i<=n;++i)
         scanf("%d", &v[i]);
	
	best[n]=1;
	poz[n]=-1;
	p=n;
	for (i=n-1;i>=1;--i)
	{
		best[i]=1;
		poz[i]=-1;
		for (j=i+1;j<=n;++j)
			 if (best[i]<best[j]+1 && v[i]<v[j])
			 {
				 best[i]=best[j]+1;
				 poz[i]=j;
				 if (best[i]>max)
					 max=best[i],
					 p=i;
			 }
	}
	
	printf("%d\n", max);
	scrie();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}