Cod sursa(job #1680411)

Utilizator monicalegendaLegenda Monica monicalegenda Data 8 aprilie 2016 18:51:58
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int best[100000], parent[100000];
long long v[100000];

void afis(int i){
	if(parent[i] != i){
		afis(parent[i]);
	}
	fout << v[i] << ' ';
}

int main(){

	int n, i, j;


	fin >> n;
	for(i = 0; i < n; i++){
		fin >> v[i];
	}

	best[0] = 1;
	parent[0] = 0;
	for(i = 1; i < n; i++){
		best[i] = 1;
		parent[i] = i;
		for(j = 0; j < i; j++){
			if(v[j] < v[i] && best[j] + 1 > best[i]){
				best[i] = best[j] + 1;
				parent[i] = j;
			}

		}
	}

	int lmax = 0, end = 0;
	for(i = 0; i < n; i++){
		// std::cout << best[i] << ' ';
		if(best[i] > lmax){
			lmax = best[i];
			end = i;
		}
	}

	// std::cout<<'\n';

	fout << lmax << '\n';

	afis(end);

	return 0;
}