Cod sursa(job #3192486)

Utilizator manudragoDragomir Manuel manudrago Data 12 ianuarie 2024 18:12:35
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 100001;
int scmax[NMAX], v[NMAX], n;
int nexti[NMAX];

int find_scmax(int poz){
    if(scmax[poz] != -1){
        return scmax[poz];
    }

    int bestie = 1;
    for(int i = poz + 1; i <= n; i++){
        if(v[i] > v[poz]){
            int best_scmax_for_i = find_scmax(i);
            if(best_scmax_for_i + 1 > bestie){
                bestie = best_scmax_for_i + 1;
                nexti[poz] = i;
            }
        }
    }

    scmax[poz] = bestie;
    return scmax[poz];
}


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

    int maxi = -1;
    int start_i = -1;
    for(int i = 1; i <= n; i++){
        int temp = find_scmax(i);
        if(temp > maxi){
            maxi = temp;
            start_i = i;
        }
    }

    fout << maxi << "\n";

    int i = start_i;
    while(i != -1){
        fout << v[i] << " ";
        i = nexti[i];
    }
    return 0;
}