Cod sursa(job #3194298)

Utilizator Dragos_HUDragos Huiu Dragos_HU Data 17 ianuarie 2024 17:07:01
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>

using namespace std;

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

const int N = 1e5;
int lmax[N + 1], v[N + 1];

void refac_subsir(int poz, int val, int lungime)
{
    if(lungime == 0)
        return;
    
    if(v[poz] <= val && lmax[poz] == lungime)
    {
        refac_subsir(poz - 1, v[poz] - 1, lungime - 1);
        out << v[poz] << ' ';
    }
    else
        refac_subsir(poz - 1, val, lungime);
}

int main()
{
    int n, poz_l_max = 0;

    in >> n;

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

        for(int j = 0; j < i; j++)
            if(v[j] < v[i])
                lungime_i = max(lungime_i, lmax[j]);
            
        lmax[i] = lungime_i + 1;

        if(lmax[i] > lmax[poz_l_max])
            poz_l_max = i;
    }

    out << lmax[poz_l_max] << '\n';

    refac_subsir(poz_l_max, v[poz_l_max], lmax[poz_l_max]);

}