Cod sursa(job #3317605)

Utilizator TeodoRazvanStancu Teodor-Razvan TeodoRazvan Data 24 octombrie 2025 17:09:59
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;

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

vector<int> v,dp;

void refac(int p,int l,int vm){
    if(!l) return;
    if(dp[p]==l&&v[p]<vm){
        refac(p-1,l-1,v[p]);
        fout<<v[p]<<" ";
    }else{
        refac(p-1,l,vm);
    }
}

int main(){
    int n;
    fin>>n;
    v.resize(n);
    dp.resize(n);
    int imax=0;
    for(int i=0;i<n;i++){
        fin>>v[i];
        int lmaxi=0;
        for(int j=0;j<i;j++){
            if(v[j]<v[i]){
                lmaxi=max(lmaxi,dp[j]);
            }
        }
        dp[i]=1+lmaxi;
        if(dp[i]>dp[imax]) imax=i;
    }
    fout<<dp[imax]<<'\n';
    refac(imax,dp[imax],INT_MAX);
    return 0;
}