Cod sursa(job #2607729)

Utilizator NicuCNicu Capatina NicuC Data 30 aprilie 2020 09:22:47
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>

#define NM 100001

using namespace std;

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

int a[NM], lg[NM], urm[NM], n, lgm, i, j, jm, im;

int main() {
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    lg[n] = 1;
    urm[n] = 0;
    for (i = n - 1; i >= 1; i--) {
        lgm = 0;
        jm = 0;
        for (j = i + 1; j <= n; j++)
            if (a[i] < a[j] && lg[j] > lgm) {
                lgm = lg[j];
                jm = j;
            }
        lg[i] = lgm + 1;
        urm[i] = jm;
    }
    lgm = 0;
    for (i = 1; i <= n; i++)
        if (lg[i] > lgm) {
            lgm = lg[i];
            im = i;
        }
    fout << lgm << '\n';
    i = im;
    do {
        fout << a[i] << ' ';
        i = urm[i];
    } while (i);
    return 0;
}