Cod sursa(job #1452848)

Utilizator Player1Player 1 Player1 Data 22 iunie 2015 00:31:33
Problema Subsir crescator maximal Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 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;
	}

	optimum = 0;
	for(i=1; i<N; i++){
		max = 0;
		for(j=0; j<i; j++)
			if((a[j] > max) && (a[j] < a[i])){
				max = a[j];
				best[i] = best[j] + 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!=0);

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

	return 0;
}