Cod sursa(job #3184140)

Utilizator cristibogdanPatrascu Cristian cristibogdan Data 14 decembrie 2023 16:29:12
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>

using namespace std;
int n;
int v[200005];
int dp[200005];
int prev_e[200005];
int sol[200005];
ifstream f("scmax.in");
ofstream g("scmax.out");

int main() {
    f >> n;
    for (int i = 1; i <= n; i++) {
        f >> v[i];
    }
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        int Max = 0;
        int prev_el = 0;
        for (int j = 1; j < i; j++ ){
            if (v[j] < v[i] && Max < dp[j]) {
                Max = dp[j];
                prev_el = j;
            }
            dp[i] = Max + 1;
            prev_e[i] = prev_el;
        }
    }
    g << dp[n] << '\n';
    int aux = n;
    int idx = 1;
    while(aux != 0) {
        sol[idx++] = aux;
        aux = prev_e[aux];
    }

    for (int i = dp[n]; i >= 1; i--) {
        g << v[sol[i]] << " ";
    }

}