Cod sursa(job #2938008)

Utilizator Razvan_GabrielRazvan Gabriel Razvan_Gabriel Data 11 noiembrie 2022 15:29:08
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>

using namespace std;

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

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

void refac_subsirul(int p, int val, int l){
    if(l == 0)
        return;
    if(v[p] <= val && lung[p] == l){
        refac_subsirul(p - 1, val - 1, l - 1);
        fout << v[p] << " ";
    }else
        refac_subsirul(p - 1, val, l);
}

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

    int p = 0;
    for(int i = 0; i < n; i++){
        lung[i] = 0;
        for(int j = 0; j < i; j++){
            if(v[j] < v[i])
                lung[i] = max(lung[i], lung[j]);
        }
        lung[i]++;
        if(lung[i] > lung[p])
            p = i;
    }

    fout << lung[p] << "\n";
    refac_subsirul(p, v[p], lung[p]);

    return 0;
}