Cod sursa(job #741960)

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

using namespace std;

#define NMAX 100000

int A[NMAX], dp[NMAX], prev[NMAX], N;
int sol[NMAX], ctr = 0;
ifstream in("scmax.in");
ofstream out("scmax.out");

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;
	out << max << endl;
	print_rec(posmax);
}

int main(){
    in >> N;
	for(int i = 0; i < N; ++i)
		in >> A[i];
        
	solve();
	print_solution();
    for(int i = ctr - 1; i >= 0; --i)
        out << A[sol[i]] << " ";
	return 0;
}