Cod sursa(job #599019)

Utilizator dspMihaiDespotovici Mihai dspMihai Data 27 iunie 2011 19:29:38
Problema Subsir crescator maximal Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <stdio.h>
using namespace std;
long j,i,N,crt,nr[100001],max[100001],gmax,sf;

int main ()
{
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	scanf("%d", &N);
	for (i=1; i<=N; i++)
	{
		scanf("%d", &nr[i]);
	}
	for (i=N; i>=1; i--)
	{
		max[i]=1;
		gmax=0;
		for (j=N; j>=i+1; j--)
			if (nr[i]<nr[j] && max[j]>max[gmax]) gmax=j;
		if (gmax) max[i]=max[gmax]+1;
		if (max[i]>max[sf]) sf=i;
	}
	printf("%d\n%d ", max[sf], nr[sf]);
	crt=nr[sf];
	for (i=sf; i<=N; i++) 
		if (nr[i]>crt)
		{
			printf("%d ", nr[i]);
			crt=nr[i];
		}
	return 0;
}