Cod sursa(job #3339437)

Utilizator AlekuwAlexandru Stefan Pascut Alekuw Data 8 februarie 2026 09:08:04
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");

const int NMAX = 1e5 + 1;

int n, dp[NMAX], tati[NMAX], v[NMAX], maxim, sol, pos, posol;

void drum(int posol) {
    if (posol != 0) {
        drum(tati[posol]);
        out << v[posol] << " ";
    }

}

int main()
{
    in >> n;
    for (int i = 1; i <= n; ++i)
        in >> v[i];
    dp[1] = 1;
    for (int i = 2; i <= n; ++i){
        int maxim;
        for (int j = 1; j < i; ++j) {
            if (v[j] < v[i] && maxim < dp[j]) {
                pos = j;
                maxim = dp[j];
            }
        }
        dp[i] = maxim + 1;
        if (dp[i] != 1)
            tati[i] = pos;
        if (sol < dp[i]) {
            sol = dp[i];
            posol = i;
        }

    }
    out << sol << "\n";
    drum(posol);
    return 0;
}