Cod sursa(job #2959246)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 30 decembrie 2022 12:39:21
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>

using namespace std;

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

const int Nmax = 100000;

int v[Nmax], best[Nmax], prv[Nmax];

void reconst(int x){

    if(prv[x] == -1){
        fout << v[x] << " ";
        return;
    }

    reconst(prv[x]);

    fout << v[x] << " ";
}

int main()
{
    int n, lenmax, x;
    bool ok;

    fin >> n;

    lenmax = 0;
    x = 0;
    for(int i = 0; i < n; i++){
        fin >> v[i];

        ok = 0;
        for(int j = 0; j < i; j++){
            if(v[i] > v[j]){
                if(best[i] < best[j] + 1){
                    best[i] = best[j] + 1;
                    prv[i] = j;
                    ok = 1;
                }
            }
        }

        if(ok == 0){
            best[i] = 1;
            prv[i] = -1;
        }

        if(lenmax < best[i]){
            lenmax = best[i];
            x = i;
        }
    }

    fout << lenmax << '\n';

    reconst(x);

    return 0;
}