Cod sursa(job #2254091)

Utilizator DRLDRLRaul Ronald Galea DRLDRL Data 4 octombrie 2018 19:30:59
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#pragma once

#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

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

vector<int> sir, dp, pp, calculat;

// td n calculeaza lis care se termina in sir[n]

int td(vector<int> &v, int n) {
	if (n == 0)
		return 1;

	if (calculat[n] == 0) {
		int iMax = 0;
		for (int i = 0; i < n; i++) {
			int result = td(v, i);
			if (v[n] > v[i]) {
				if (iMax < result) {
					iMax = result;
					pp[n] = i;
				}
			}
		}
		calculat[n] = 1;
		dp[n] = iMax + 1;
	}
	return dp[n];
}

int main() {
	vector<int> sol;
	int n, lis = -1, pos = -1;
	fin >> n;
	pp.resize(n);
	sir.resize(n);
	dp.resize(n);
	calculat.resize(n);
	for (int i = 0; i < n; i++) {
		fin >> sir[i];
		dp[i] = 1; // base
	}
	td(sir, n - 1);
	for(int i = 0; i<dp.size(); i++)
		if (dp[i] > lis) {
			lis = dp[i];
			pos = i;
		}
	fout << lis << "\n";
	while (lis) {
		sol.push_back(sir[pos]);
		pos = pp[pos];
		lis--;
	}
	reverse(sol.begin(), sol.end());
	for (int i = 0; i < sol.size(); i++)
		fout << sol[i] << " ";
	return 0;
}