Cod sursa(job #357451)

Utilizator ooctavTuchila Octavian ooctav Data 19 octombrie 2009 12:19:14
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
int e[100001],n,l=0;
int sir[100001];
int pred[100001],el[100001];
int sirmax=0,poz;


void citire()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&e[i]);
}


void constr()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<i;j++)
			if(sir[i]<sir[j] && e[i]>e[j])
			{
				sir[i]=sir[j];
				pred[i]=j;
			}
		sir[i]++;
	}
}


void obtmax()
{
	for(int i=1;i<=n;i++)
		if(sir[i]>sirmax)
		{
			sirmax=sir[i];
			poz=i;
		}
}


void formare()
{
	int poz2=poz;
	while(poz2)
	{
		el[++l]=poz2;
		poz2=pred[poz2];
	}
}


void scriere()
{
	printf("%d\n",l);
	for(int i=l;i>=1;i--)
		printf("%d ",e[el[i]]);
}

int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	
	citire();
	constr();
	obtmax();
	formare();
	scriere();
	
	return 0;
}