Cod sursa(job #454833)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 12 mai 2010 17:14:58
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cstdio>

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

int n,v[101000],best[101000],poz[101000],max,p;

void citire()
{
	int i;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
	for (i=1;i<=n;++i)
		 scanf("%d", &v[i]);
}

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

void solve()
{
	int i,j;
	
	best[n]=1;
	poz[n]=-1;
	
	for (i=n-1;i>=1;--i)
	{
		best[i]=1;
		poz[i]=-1;
		for (j=i+1;j<=n;++j)
			 if (v[i]<v[j] && best[i]<best[j]+1)
			 {
				 best[i]=best[j]+1;
				 poz[i]=j;
			 }
		if (best[i]>max)
			max=best[i],
			p=i;
	}

	printf("%d\n", max);
	scrie();
}

int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}