Cod sursa(job #3277889)

Utilizator SwanOCPica Razvan Mihai SwanOC Data 17 februarie 2025 19:42:59
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in("scmax.in");
ofstream out("scmax.out");

int n, lmax, last_idx, indices[100010], v[100010], dp[100010];

void reconstruct(int idx) {
    if (idx == -1)
        return;
    
    reconstruct(indices[idx]);
    out << v[idx] << " ";
}

int main(void) {
    in >> n;
    for (int i = 1; i <= n; i++) {
        in >> v[i];
        dp[i] = 1;
        indices[i] = -1;
    }

    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++)
            if (v[j] < v[i] && dp[i] < 1 + dp[j]) {
                    dp[i] = 1 + dp[j];
                    indices[i] = j;
                }
    
        if (dp[i] > lmax) {
            lmax = dp[i];
            last_idx = i;
        }
    }

    out << lmax << '\n';
    reconstruct(last_idx);

    return 0;
}