Cod sursa(job #1101188)

Utilizator alex.muscaluAlexandru Muscalu alex.muscalu Data 7 februarie 2014 23:58:32
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

int main(){

	fstream file;
	int Lmax, n, pos;
	file.open("scmax.in", ios::in);
	file >> n;
	vector<int> v(n), length(n), pre(n);
	for (int i = 0; i < n; i++){
		file >> v[i];
	}
	length[n - 1] = 1;
	pre[n - 1] = 0;
	for (int i = n - 2; i >= 0; i--){
		Lmax = 0;
		pos = 0;
		for (int k = n-1; k > i; k--){
			if (v[i] < v[k] && Lmax < length[k] + 1){
				pos = k;
				Lmax = length[k] + 1;
			}
		}
		length[i] = Lmax;
		pre[i] = pos;
	}
	file.close();
	file.open("scmax.out", ios::out);
	int max = length[0], k = 0;
	for (int i = 1; i < n; i++){
		if (max < length[i]){
			max = length[i];
			k = i;
		}
	}
	file << max << endl;
	file << v[k] << " ";
	k = pre[k];
	while (k != 0){
		file << v[k]<<" ";
		k = pre[k];
	}
	return 0;
}