Cod sursa(job #2722913)

Utilizator marius004scarlat marius marius004 Data 13 martie 2021 13:06:48
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 100001;
int n, dp[NMAX], arr[NMAX], tree[NMAX], maxxIndex;

void reconstruct(int index) {

    if(index == -1)
        return;

    reconstruct(tree[index]);
    g << arr[index] << ' ';
}

int main() {

    f >> n;

    for(int i = 1;i <= n;++i)
        f >> arr[i], tree[i] = -1;

    dp[1] = 1;
    for(int i = 2;i <= n;++i) {

        dp[i] = 1;

        for (int j = 1; j < i; ++j) {
            if (arr[j] < arr[i] && dp[i] < 1 + dp[j]) {
                dp[i] = 1 + dp[j];
                tree[i] = j;
            }
        }

        if(dp[maxxIndex] < dp[i])
            maxxIndex = i;
    }

    g << dp[maxxIndex] << '\n';

    reconstruct(maxxIndex);

    return 0;
}