Cod sursa(job #1864395)

Utilizator tudormaximTudor Maxim tudormaxim Data 31 ianuarie 2017 18:56:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
using namespace std;

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

const int maxn = 1e5 + 5;
int V[maxn], Best[maxn], Pre[maxn];

int main() {
    ios_base :: sync_with_stdio (false);
    int n, i, j, maxx, p;
    fin >> n;
    for (i = 1; i <= n; i++) {
        fin >> V[i];
    }
    Best[n] = 1;
    Pre[n] = -1;
    maxx = 1;
    p = n;
    for (i = n - 1; i; i--) {
        Best[i] = 1;
        Pre[i] = -1;
        for (j = i + 1; j <= n; j++) {
            if (Best[j] + 1 > Best[i] && V[j] > V[i]) {
                Best[i] = Best[j] + 1;
                Pre[i] = j;
            }
            if (Best[i] > maxx) {
                maxx = Best[i];
                p = i;
            }
        }
    }
    fout << maxx << "\n";
    i = p;
    while (i != -1) {
        fout << V[i] << " ";
        i = Pre[i];
    }
    fin.close();
    fout.close();
    return 0;
}