Cod sursa(job #1101180)

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

void 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 = i + 1; k < n; 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];
	}

}