Cod sursa(job #3168120)

Utilizator Robert_NicuNicu Robert Cristian Robert_Nicu Data 11 noiembrie 2023 16:19:49
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>
#define DIM 100001
using namespace std;

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

int n, p, maxim, ans, pozfinal;
int v[DIM], d[DIM], poz[DIM];
int i, j;

void drum(int x){
    if(x){
        drum(poz[x]);
        fout<<v[x]<<" ";
    }
}

int main(){
    fin>>n;
    for(i=1; i<=n; i++)
        fin>>v[i];

    d[1]=1;
    for(i=2; i<=n; i++){
        maxim=0;
        for(j=1; j<i; j++)
        if(v[j]<v[i] && d[j]>maxim){
            maxim=d[j];
            p=j;
        }
        d[i]=maxim+1;
        if(d[i]>1)
            poz[i]=p;
        if(d[i]>ans){
            pozfinal=i;
            ans=d[i];
        }
    }
    fout<<ans<<"\n";
    drum(pozfinal);
}