Cod sursa(job #2023956)

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