Cod sursa(job #2983304)

Utilizator al3x.unxUngureanu Alex al3x.unx Data 22 februarie 2023 10:00:06
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
using namespace std;
const int NMAX = 6;

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

int a[NMAX] = {0}, l[NMAX] = {0}, sol[NMAX] = {0};
// l[i] = cel mai lung subsir crescator care se termina in a[i]

// Pasul 2: reconstituirea sirului

void recsir(int i) {
    if (i == 0) {
        return;
    } else {
        recsir(sol[i]);
        fout << a[i] << ' ';
    }
}

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

    //Pasul 1: generarea vectorului l

    int pozlmax = 0 ;

    for (int i = 1; i <= N; i++) {
        int jmax = 0;

        for (int j = i - 1; j >= 1; j--) {
            if (a[j] < a[i] && l[j] > l[jmax]) {
                jmax = j;
            }
        }

        l[i] = l[jmax] + 1;
        sol[i] = jmax;

        if (l[i] > l[pozlmax]) {
            pozlmax = i;
        }
    }

    fout << l[pozlmax] << '\n';
    recsir(pozlmax);
    return 0;
}