Cod sursa(job #3278630)

Utilizator PredaBogdanPreda Bogdan PredaBogdan Data 20 februarie 2025 12:23:49
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;

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

void afis(int v[], int mare[], int last) {
    if (last == -1) return;
    else {
        afis(v, mare, mare[last]);
        g << v[last] << ' ';
    }
}

int main(void) {
    int n, v[100001], dp[100001], mare[100001], max = -1;
    f >> n;
    for (int i = 0; i < n; i++) {
        f >> v[i];
        dp[i] = 1;
        mare[i] = -1;
    }

    int last = -1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (v[j] < v[i] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                mare[i] = j;
            }
        }

        if (dp[i] > max) {
            max = dp[i];
            last = i;
        }
    }

    g << max << '\n';
    
    afis(v, mare, last);
}