Cod sursa(job #2031052)

Utilizator raul044Moldovan Raul raul044 Data 2 octombrie 2017 17:36:54
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>

using namespace std;

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

long long n, v[100002], ln[100002], poz[100002];
int maxl = -1, maxp;


int main () {
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }
    int i , j;
    for (i = n; i > 0; i--) {
        for (j = i+1, poz[i] = -1, ln[i] = 1; j <= n; j++) {
            if (v[i] < v[j] and ln[i] < ln[j] + 1) {
                ln[i] = ln[j] + 1;
                poz[i] = j;
            }
        }
        if (ln[i] > maxl) {
            maxl = ln[i];
            maxp = i;

        }
    }

   /*for (int i = 1; i <= n; i++) {
    if (ln[i] > maxl) {
        maxl = ln[i];
        maxp = i;
    }
   }*/
    fout << maxl << '\n';
    for (i = maxp; i != -1; i = poz[i]) {
        fout << v[i] << " ";
    }
}