Cod sursa(job #741959)

Utilizator gener.omerGener Omer gener.omer Data 27 aprilie 2012 16:56:24
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>

using namespace std;

#define NMAX 100000

int A[NMAX], dp[NMAX], prev[NMAX], N;
int sol[NMAX], ctr = 0;

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){
    sol[ctr++] = pos;
    while(prev[pos] != -1){
        sol[ctr++] = prev[pos];
        pos = prev[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();
    for(int i = ctr - 1; i >= 0; --i)
        printf("%d ", A[sol[i]]);
	return 0;
}