Pagini recente » Cod sursa (job #3037658) | Cod sursa (job #2362638) | Cod sursa (job #60449) | Cod sursa (job #1779830) | Cod sursa (job #2254091)
#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;
}