Cod sursa(job #2956603)

Utilizator TheEpicWipedCreaVlad Chirita Alexandru TheEpicWipedCrea Data 19 decembrie 2022 21:18:29
Problema Subsir crescator maximal Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in  ("scmax.in");
ofstream out("scmax.out");

#define maxN 100000
int v[maxN+1];
int d[maxN+1];
int rez[maxN+1];

int main(){
    int n;
    in>>n;
    for(int i=1;i<=n;i++){
        in>>v[i];
    }
    int maxi=0,pos=-1;
    for(int i=1;i<=n;i++){
        d[i]=1;
        for(int j=1;j<=i;j++){
            if(v[j]<v[i]){
                if(d[i]<d[j]+1){
                    d[i]=d[j]+1;
                }
            }
        }
        if(maxi<d[i]){
            maxi=d[i];
            pos=i;
        }
    }
    out<<maxi<<'\n';
    int nr=1;
    rez[nr]=v[pos];
    for(int i=pos;i>=1 && nr<maxi;i--){
        if(v[i]<v[pos]){
            nr++;
            rez[nr]=v[i];
            pos=i;
        }
    }
    for(int i=maxi;i>=1;i--){
        out<<rez[i]<<" ";
    }
}