Cod sursa(job #1292994)

Utilizator robert_fanrRobert Banu robert_fanr Data 15 decembrie 2014 09:12:30
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");

int n, v[100001], lung[100001], pred[100001];

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

void subsir(int p) {
    if(pred[p] != 0)
        subsir(pred[p]);
    out << v[p] << " ";
}

int main()
{
    citire();
    int i, j, j0, maxim=0;
    lung[0] = 0;
    lung[1] = 1;
    for (i=2; i<=n; i++) {
        j0 = 0;
        for (j=1; j<i; j++)
            if(v[j] < v[i] && lung[j] > lung[j0])
                j0 = j;
        lung[i] = 1 + lung[j0];
        pred[i] = j0;
        if (lung[i] > lung[maxim])
            maxim = i;
    }

    out << lung[maxim] <<"\n";
    subsir(maxim);

    return 0;
}