Pagini recente » Cod sursa (job #595909) | Cod sursa (job #3126069) | Cod sursa (job #3124297) | Monitorul de evaluare | Cod sursa (job #2023936)
// Example program
#include <iostream>
#include <fstream>
#include <string>
int constexpr MAXN = 100001;
int cache[MAXN], a[MAXN], back[MAXN];
int dp(int i) {
if (cache[i] > 0) {
return cache[i];
}
int max = 0, new_val = 1;
for (int j = 0; j < i; ++j) {
new_val = dp(j) + (a[j] < a[i]);
if (new_val > max) {
max = new_val;
back[i] = j;
}
}
cache[i] = new_val;
return cache[i];
}
int main()
{
int n;
std::ifstream in("scmax.in");
std::ofstream out("scmax.out");
in >> n;
for (int i = 0; i < n; ++i)
in >> a[i];
int scmax = dp(n - 1);
int scmax_copy = scmax;
out << scmax << "\n";
int curr = n - 1;
while (curr) {
cache[--scmax] = curr;
curr = back[curr];
}
for (int i = 0; i < scmax_copy; ++i)
out << a[cache[i]] << " ";
out << "\n";
return 0;
}