Cod sursa(job #1430921)

Utilizator deleted_45f432468e7cd611DELETED deleted_45f432468e7cd611 Data 8 mai 2015 22:04:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>

void maxSeq (std::vector<int> &v, int n) {
	std::vector<int> maxim (n, 1);
	std::vector<int> next (n, - 1);

	std::vector<int> maxSubsequence;

//	maxim[n-1] = 1;
//	next[n-1] = -1;

	for (int i = n - 2; i >= 0; --i) {
	//	maxim[i] = 1;
	//	next[i] = -1;

		for (int j = i + 1; j < n; ++j) {
			if (v[i] < v[j] && maxim[i] <= maxim[j]) {
				maxim[i] = maxim[j] + 1;
				next[i] = j;
			}
		}
	}

	int len = maxim[0];
	int startFrom = 0;

	for (int i = 1; i < n; ++i) {
		if (len < maxim[i]) {
			len = maxim[i];
			startFrom = i;
		}
	}

	maxSubsequence.push_back (v[startFrom]);

	for (int i = 1; i < n; ++i) {
		startFrom = next[startFrom];
		maxSubsequence.push_back (v[startFrom]);
	}

	std::ofstream g ("scmax.out");
	g << len << "\n";

	for (int i = 0; i < len; ++i) {
		g << maxSubsequence[i] << " ";
	}
	g << "\n";
	g.close();
	
	maxim.clear();
	next.clear();
	maxSubsequence.clear();
}

int main (void) {
	std::ifstream f ("scmax.in");
	int n;

	f >> n;

	std::vector<int> v (n, 0);

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

	maxSeq (v, n);

	v.clear();
	f.close();
	return 0;
}