Cod sursa(job #1452855)

Utilizator Player1Player 1 Player1 Data 22 iunie 2015 01:01:56
Problema Subsir crescator maximal Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <stdio.h>

int main(){
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);

	long long N, i, j, x, max, index, optimum;
	long long a[100003], best[100003], before[100003];
	
	scanf("%lld ", &N);

	for(i=0; i<N; i++){
		scanf("%lld ", &a[i]);
		best[i] = 1;
		before[i] = -1;
	}

	optimum = 0;
	for(i=1; i<N; i++){
		max = 0;
		for(j=0; j<i; j++)
			if(a[j] < a[i]){
				if(best[j] > max)
					max = best[j];
				best[i] = max + 1;  
				before[i] = j;
				if(best[i] > optimum){
					optimum = best[i];
					index = i;
				}
			}
	}

	j=0;
	do{
		best[j] = a[index];
		index = before[index];
		j++;
	}while(index!=-1);

	printf("%lld\n",optimum);
	for(i=j-1; i>=0; i--)
		printf("%lld ", best[i]);

	return 0;
}