Cod sursa(job #3002346)

Utilizator Paul281881818818181991919191881818Draghici Paul Paul281881818818181991919191881818 Data 14 martie 2023 17:45:10
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <vector>
std::ifstream fin("scmax.in");
std::ofstream fout("scmax.out");
int n;
std::vector<int> V, best, poz;
void compute(){
    best[n] = 1;
    poz[n] = -1;
    int next = n, max = 1;
    for(int i = n - 1; i >= 1; i--){
        best[i] = 1;
        poz[i] = -1;
        for(int j = i + 1; j <= n; j++){
            if(V[i] < V[j] && best[i] < best[j] + 1){
                best[i] = best[j] + 1;
                poz[i] = j;
                if(max < best[i]){
                    max = best[i];
                    next = i;
                }
            }
        }
    }
    fout << max << "\n";
    while(next != -1){
        fout << V[next] << " ";
        next = poz[next];
    }
}
int main(){
    fin >> n;
    V = best = poz = std::vector<int> (n + 1);
    for(int i = 1; i <= n; i++){
        fin >> V[i];
    }
    compute();
}