Cod sursa(job #3315228)

Utilizator vledimir2024Voicu Vladimir Nicolae vledimir2024 Data 13 octombrie 2025 09:30:12
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
 using namespace std;

int main(){
    int N;
    long long a[100],dp[100],parent[100];

    ifstream f("scmax.in");
    ofstream g("scmax.out");

    f>>N;
    for(int i=0;i<N;i++){
        f>>a[i];
        dp[i]=1;
        parent[i]=-1;
    }

    int Lmax=1,last=0;
    for(int i=1;i<N;i++){
        for(int j=0;j<i;j++){
            if(a[i]>a[j] && dp[j]+1 >dp[i]){
                dp[i] = dp[j] +1;
                parent[i] = j;
            }
        }
        if(dp[i]>Lmax){
            Lmax = dp[i];
            last = i;
        }
    }

    long long lis[100];
    int k=0;
    for(int i=last;i!=-1; i=parent[i]) lis[k++] =a[i];

    g<<Lmax<<"\n";
    for(int i = k-1; i>=0;i--)
        g<<lis[i]<<" ";
    g<<"\n";

    f.close();
    g.close();
    return 0;

}