Cod sursa(job #3281168)

Utilizator ankaramessiankaramessi ankaramessi Data 28 februarie 2025 15:18:22
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ll long long
#define NMAX 100005
#define INF 1000000000
#define MOD 666013

int v[NMAX], dp[NMAX], venit[NMAX];
bool marked[NMAX];

vector <int> sol;

int main() {
    ifstream cin("scmax.in");
    ofstream cout("scmax.out");
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        dp[i] = 1;
    }
    int ans = 0, index = 0;
    for (int i = 2; i <= n; i++) {
        for (int j = i - 1; j >= 1; j--) {
            if (v[i] > v[j] && dp[j] + 1 > dp[i]) {
                venit[i] = j;
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > ans) {
            ans = dp[i];
            index = i;
        }
    }
    cout << ans << '\n';

    while (index != 0) {
        sol.pb(v[index]);
        index = venit[index];
    }
    reverse(sol.begin(), sol.end());
    for (int x: sol) cout << x << " ";
    return 0;
}