Cod sursa(job #3241990)

Utilizator vlad7654vladimir manescu vlad7654 Data 7 septembrie 2024 10:19:39
Problema Subsir crescator maximal Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int main(){
    int n;
    fin>>n;
    vector<int> v(n+1), max1(n+1), pre1(n+1);
    for(int i=1;i<=n;i++){
        fin>>v[i];
        int cnt=0;
        for(int j=1;j<i;j++){
            if(v[j]<v[i]){
                pre1[i]=j;
                cnt=max(cnt, max1[j]);
            }
        }
        max1[i]=cnt+1;
    }
    int i=n;
    vector<int> ans;
    ans.push_back(v[i]);
    while(i>0){
        if(pre1[i]!=0){
            ans.push_back(v[pre1[i]]);
        }
        i=pre1[i];
    }
    fout<<*max_element(max1.begin(),max1.end())<<'\n';
    reverse(ans.begin(),ans.end());
    for(int i:ans){
        fout<<i<<' ';
    }
}