Cod sursa(job #3339435)

Utilizator Pep3Rares Popa Pep3 Data 8 februarie 2026 09:01:33
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int v[100001], t[100001], dp[100001];
int sol, u;

void drum(int poz) {
    if (poz == 0) return;
    drum(t[poz]);
    out << v[poz] << " ";
}

int main() {
    int n;
    in >> n;

    for (int i = 1; i <= n; i++) {
        in >> v[i];
    }

    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        t[i] = 0;
        int maxim = 0;
        int p = 0;
        for (int j = 1; j < i; j++) {
            if (v[j] < v[i] && dp[j] > maxim) {
                maxim = dp[j];
                p = j;
            }
        }
        dp[i] = maxim + 1;
        t[i] = p;

        if (dp[i] > sol) {
            sol = dp[i];
            u = i;
        }
    }

    out << sol << "\n";
    drum(u);

    return 0;
}