Cod sursa(job #1665074)

Utilizator TiberiuDTiberiu Danciu TiberiuD Data 26 martie 2016 16:01:38
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>

using namespace std;

int v[100000], lung[100000], pred[100000];
ifstream in("scmax.in");
ofstream out("scmax.out");

void sir(int p) {
    if(pred[p] != 0)
        sir(pred[p]);

    out << v[p] << " ";
}

int main() {
    /*
     * se da un sir de numere intregi. (v[1], v[2],...v[n])
     * se cere un subsir strict crescator de lungime maxima
     * (v[i1], v[i2], v[i3] ..., v[ik] cu i1 < i2 < i3...
     * si v[i1] < v[i2] etc

     * Ex
     * v = 5 2 4 1 6 3 4 9 5 8 4
     *       ^       ^ ^   ^ ^
     *           ^   ^ ^   ^ ^

     * lung[i] = lungimea celui mai mare subsir strict crescator
     * care se termina pe pozitia i
     *
     * lung = (1, 1, 2, 1, 3, 2, 3, 4, 4, 5, 3)
     *
     * pred = (0, 0, 2, 0, 3, 2, 3, 5, 7, 9, 6)
     *
     *
     *

    */

    int n;
    in >> n;
    for(int i = 1; i <= n; i++)
        in >> v[i];

    lung[1] = 1;
    pred[1] = 0;
    int 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;
    }

    out << lung[pmax] << "\n";
    sir(pmax);

    return 0;
}