Cod sursa(job #1866560)

Utilizator roxannemafteiuMafteiu-Scai Roxana roxannemafteiu Data 3 februarie 2017 12:17:52
Problema Subsir crescator maximal Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;

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

const int N_MAX = 1e5 + 5;
const int INF = 0;

int n;
vector <int> v, sol;

int main() {
    fin >> n;

    int dp[n + 1];
    memset(dp, 1, sizeof dp);

    for (int i = 0; i < n; ++i) {
        int x;
        fin >> x;
        v.emplace_back(x);

        int maxdp = -INF;
        for (int j = i - 1; j >= 0; --j) {
            if (v[j] < v[i] && maxdp < dp[j]) {
                maxdp = dp[j];
            }
        }

        dp[i] = 1 + maxdp;
    }

    int maxim = -INF, pozmax;
    for (int i = 0; i < n; ++i) {
        if (maxim < dp[i]) {
            maxim = dp[i];
            pozmax = i;
        }
    }

    fout << maxim << "\n";

    int maxdpj = -INF, j = pozmax - 1;
    sol.emplace_back(v[pozmax]);
    while (j > 0) {
        if (v[j] < v[pozmax] && dp[j] == dp[pozmax] - 1) {
                pozmax = j;
                sol.emplace_back(v[j]);

        }
        --j;
    }

    reverse(sol.begin(), sol.end());
    for (const auto &s : sol) {
        fout << s << " ";
    }

    return 0;

}