Cod sursa(job #427272)

Utilizator nashnash mit nash Data 27 martie 2010 18:12:34
Problema Subsir crescator maximal Scor 30
Compilator c Status done
Runda Arhiva educationala Marime 0.62 kb
#include <stdio.h>

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

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--) {
		l[i] = 1;
		tata[i] = 0;
		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;
}