Cod sursa(job #1890917)

Utilizator luanastLuana Strimbeanu luanast Data 23 februarie 2017 16:32:06
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>

using namespace std;

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


int v[100010], T[100010], L[100010];
int n, i, maxim, pmaxim, M, poz, j;;

void drum(int poz) {
    if (poz != 0) {
        drum(T[poz]);
        fout<<v[poz]<<" ";
    }
}

int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v[i];
    }

    // calculam in L[i] = lungimea maxima a unui subsir crescator terminat chiar cu v[i]
    L[1] = 1;

    for (i=2;i<=n;i++) {
        maxim = 0;
        pmaxim = 0;
        for (j=1;j<i;j++)
            if (v[i] > v[j] && L[j] > maxim) {
                maxim = L[j];
                pmaxim = j;
            }

        L[i] = 1 + maxim;
        if (L[i] >= 2)
            T[i] = pmaxim;


        if (L[i] > M) {
            M = L[i];
            poz = i;
        }

    }


    fout<<M<<"\n";
    drum(poz);


}