Cod sursa(job #3202857)

Utilizator Iustin2812Ion Iustin Ciprian Iustin2812 Data 12 februarie 2024 14:11:30
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int v[100001],n,dp[100001];
int smax=0,maxi;

void sDp(int d){
    
    int k=d-1;
    int ok=0;
    while(dp[k]==maxi&&k>=1){
        if(v[d]>v[k]){
            dp[d]=dp[k]+1;
            maxi=dp[d];
            ok=1;
            break;
        }
        k--;
    }
    if(ok==0)
        dp[d]=dp[d-1];
}

int main(){
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i];
    }
    dp[1]=1;
    maxi=1;
    for(int i=2;i<=n;i++){
        sDp(i);
    }
    fout<<maxi<<endl;
    int k=1;
    for(int i=1;i<n;i++){
        if(dp[i+1]>dp[i])
            fout<<v[i]<<" ";
    }
    if(dp[n]>dp[n-1])
        fout<<v[n];
    return 0;
}