Cod sursa(job #2397284)

Utilizator eduardcadarCadar Eduard eduardcadar Data 4 aprilie 2019 11:57:40
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <iostream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n, a[100001], poz[100001], dp[100001], b[100001], imax, maxi;
int main()
{
    f >> n;
    for (int i = 1; i <= n; ++i) f >> a[i];
    dp[1] = 1;
    poz[1] = poz[0] = 0;
    for (int i = 2; i <= n; ++i) {
        dp[i] = 1;
        poz[i] = 0;
        for (int j = 1; j < i; ++j)
        if (a[i] > a[j] && dp[j] + 1 > dp[i]) {
            dp[i] = dp[j] + 1;
            poz[i] = j;
        }
        if (maxi < dp[i]) {
            maxi = dp[i];
            imax = i;
        }
    }
    g << maxi << '\n';
    int k = 0;
    for (int i = imax; i; i = poz[i]) b[++k] = a[i];
    for (int i = k; i; --i) g << b[i] << ' ';
    g << '\n';
    return 0;
}