Cod sursa(job #1665087)

Utilizator vlad00Vlad Stoleru vlad00 Data 26 martie 2016 16:10:58
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>
#define NMAX 1000005

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

int v[NMAX], lung[NMAX], pred[NMAX], pmax, n;

void sir(int p) {
    if (pred[p])
        sir(pred[p]);
    g << v[p] << ' ';
}

int main() {
    f >> n;
    for (int i = 1; i <= n; ++i)
        f >> v[i];
    lung[1] = 1, pred[1] = 0, pmax = 1;
    for (int i = 2; i <= n; ++i) {
        lung[i] = 0;
        for (int j = 1; j < i; ++j)
            if (v[j] < v[i])
                if (lung[j] > lung[i]) {
                    lung[i] = lung[j];
                    pred[i] = j;
                }
        lung[i]++;
        if (lung[i] > lung[pmax])
            pmax = i;
    }
    g << lung[pmax] << '\n';
    sir(pmax);
    return 0;
}