Cod sursa(job #2700547)

Utilizator ionut98Bejenariu Ionut Daniel ionut98 Data 28 ianuarie 2021 01:01:21
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include<fstream>
#include<deque>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");

int n, a[100002], pre[100002], best[100002], poz;
deque<int> sol;

void citire(){
    f >> n;
    for(int i = 1;i <= n;i++){
        f >> a[i];
    }
}

void scmax(){
    best[1] = 1;
    poz = 1;
    for(int i = 2;i <= n;i++){
        best[i] = 1;
        for(int j = 1;j < i;j++){
            if(a[j] < a[i] && best[j]+1 > best[i]){
                best[i] = best[j] + 1;
                pre[i] = j;
            }
        }
        if(best[i] > best[poz]){
            poz = i;
        }
    }
}

void afisare(){
    g << best[poz] << "\n";
    while(poz){
        sol.push_front(poz);
        poz = pre[poz];
    }
    while(!sol.empty()){
        g << a[sol.front()] << " ";
        sol.pop_front();
    }
}

int main(){
    citire();
    scmax();
    afisare();
    return 0;
}