Cod sursa(job #2765585)

Utilizator ps2001Silviu Popescu ps2001 Data 28 iulie 2021 11:15:17
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

int main()
{
    ifstream fin("scmax.in");
    ofstream fout("scmax.out");

    int n;
    fin >> n;

    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++)
        fin >> v[i];

    vector<pair<int, int>> dp(n + 1);

    int maxim = 1;
    for (int i = 1; i <= n; i++) {
        int best = 0;

        for (int j = 1; j < i; j++) {
            if (v[j] < v[i]) {
                if (dp[j].first > dp[best].first) {
                    best = j;
                }
            }
        }

        dp[i].first = 1 + dp[best].first;
        dp[i].second = best;

        if (dp[i].first > dp[maxim].first)
            maxim = i;
    }

    vector<int> sol;
    int pos = maxim;

    while (pos != 0) {
        sol.push_back(v[pos]);
        pos = dp[pos].second;
    }

    reverse(sol.begin(), sol.end());

    fout << sol.size() << '\n';
    for (auto &x : sol) {
        fout << x << ' ';
    }

    fout << '\n';

    return 0;
}