Cod sursa(job #2023936)

Utilizator RaduDoStochitoiu Radu RaduDo Data 19 septembrie 2017 18:16:15
Problema Subsir crescator maximal Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
// 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;
}