Cod sursa(job #2878870)

Utilizator preda.andreiPreda Andrei preda.andrei Data 28 martie 2022 01:11:55
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>

using namespace std;

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

    int n;
    fin >> n;

    vector<int> vec(n);
    for (auto& num : vec) {
        fin >> num;
    }

    vector<int> dp(n, 1);
    vector<int> prev(n, -1);
    for (int i = 1; i < n; i += 1) {
        for (int j = 0; j < i; j += 1) {
            if (vec[i] > vec[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
    }

    int index = 0;
    for (int i = 1; i < n; i += 1) {
        if (dp[i] > dp[index]) {
            index = i;
        }
    }

    fout << dp[index] << "\n";

    vector<int> res(dp[index]);
    for (int i = res.size() - 1; i >= 0; i -= 1) {
        res[i] = vec[index];
        index = prev[index];
    }
    for (const auto& num : res) {
        fout << num << " ";
    }
    fout << "\n";

    return 0;
}