Cod sursa(job #427257)

Utilizator nashnash mit nash Data 27 martie 2010 18:01:20
Problema Subsir crescator maximal Scor 5
Compilator c Status done
Runda Arhiva educationala Marime 0.57 kb
#include <stdio.h>

int n,vec[100001],tata[100001],i,j,l[100001];

int main() {
	
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	
	scanf("%d",&n);
	
	for(i = 1 ; i <= n ; i++ )
		scanf("%d",&vec[i]);
	
	l[n] = 1;
	tata[n] = 0;
	
	for(i = n-1 ; i >= 1 ; i--)
		for(j = i + 1 ; j <= n ; j++)
			if( (vec[i] < vec[j]) && (l[i] < l[j] + 1) )
				l[i] = l[j] + 1 , tata[i] = j;
	
	int sol = 1;
	
	for(i =	2; i<= n; i++)
		if(l[sol] < l[i])
			sol = i;
	
	printf("%d\n",l[sol]);
	
	do {
		printf("%d ",vec[sol]);
		sol = tata[sol];
	}while( sol == 0 );
	
	return 0;
}