Cod sursa(job #711321)

Utilizator gener.omerGener Omer gener.omer Data 11 martie 2012 21:50:20
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <cstdio>

using namespace std;

#define NMAX 100000

int A[NMAX], dp[NMAX], prev[NMAX], N;

void solve(){
	dp[0] = 1;
	prev[0] = -1;
	for(int i = 1; i < N; ++i){	
		int p, max = -1;
		for(int j = 0; j < i; ++j)
			if(A[i] > A[j] && ((dp[j] + 1) > max)){
				max = dp[j] + 1;
				p = j;
			}
		if(max != -1){
			dp[i] =  max;
			prev[i] = p;
		}
		else{
			dp[i] = 1;
			prev[i] = -1;
		}
	}		
}

void print_rec(int pos){
	if(prev[pos] != -1)
		print_rec(prev[pos]);
	printf("%d ", A[pos]);
}

void print_solution(){
	int posmax, max = 0;
	for(int i = 0; i < N; ++i)	
		if(dp[i] > max) 
			max = dp[i], posmax = i;
	printf("%d\n", max);
	print_rec(posmax);
}

int main(){
	freopen("scmax.in", "rt", stdin);
	freopen("scmax.out", "wt", stdout);
	scanf("%d", &N);
	for(int i = 0; i < N; ++i)
		scanf("%d", &A[i]);
	solve();
	print_solution();
	return 0;
}