Cod sursa(job #680357)

Utilizator tiriplicamihaiTiriplica Mihai Dragos tiriplicamihai Data 15 februarie 2012 14:54:12
Problema Subsir crescator maximal Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 0.7 kb
#include<stdio.h>

#define MaxN 100002

int main(){
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	int a[MaxN], N, i, max, poz, l[MaxN], j;

	scanf("%d", &N);
	for(i = 0; i < N; i++){
		scanf("%d", &a[i]);
		l[i] = 0;
	}
	l[N-1] = 1;
	for(i = N-2; i >= 0; i--){
		max = 0;
		for(j = i; j < N; j++)
			if(a[i] < a[j] && max < l[j])
				max = l[j];
		l[i] = 1 + max;
	}
	
	max = l[0];
	poz = 0;
	for(i = 1; i < N; i++)
		if(l[i] > max){
			max = l[i];
			poz = i;
		}
	printf("%d\n", max);
	printf("%d ", a[poz]);
	max--;
	while(max){
		for(i = poz; i < N; i++)
			if(l[i] == max){
				poz = i;
				break;
			}
		printf("%d ", a[poz]);
		max--;
	}
	printf("\n");
	fclose(stdin);
	fclose(stdout);
}