Pagini recente » Cod sursa (job #1502718) | Cod sursa (job #2023956)
// Example program
#include <iostream>
#include <fstream>
#include <string>
int constexpr MAXN = 100001;
int cache[MAXN], a[MAXN], back[MAXN];
int global_max, global_i;
int dp(int i) {
if (cache[i] > 0) {
return cache[i];
}
int max = 0, new_val = 1;
for (int j = 0; j < i; ++j) {
if (a[j] < a[j]) {
new_val = dp(j) + 1;
if (new_val > max) {
max = new_val;
back[i] = j;
}
}
}
cache[i] = new_val;
if (cache[i] > global_max) {
global_max = cache[i];
global_i = i;
}
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];
dp(n - 1);
int scmax_copy = global_max;
out << global_max << "\n";
int curr = global_i;
while (curr) {
cache[--global_max] = curr;
curr = back[curr];
}
for (int i = 0; i < scmax_copy; ++i)
out << a[cache[i]] << " ";
out << "\n";
return 0;
}