Cod sursa(job #3037500)

Utilizator Vlad_NistorNIstor Vlad Vlad_Nistor Data 25 martie 2023 17:09:22
Problema Subsir crescator maximal Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
using namespace std;


int tatic[100001];
int dp[100001];
int a[100001];

void reconst(int t){
    if(tatic[t]){
        reconst(tatic[t]);
        cout << a[t] << ' ';
    }else{
        cout << a[t] << ' ';
    }
}

int main(void){
    ofstream cout("scmax.out");
    ifstream cin("scmax.in");
    int n;
    cin >> n;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
    }
    dp[1] = 1;
    int maxim = -1, poz = 0;
    for(int i = 1;i<=n;i++){
        int pz = 0, maxi = 0;
        for(int j = i-1;j>=1;j--){
            if(a[i] > a[j]){
                if(maxi < dp[j]){
                    maxi = dp[j];
                    pz = j;
                }
            }
        }
        dp[i] = maxi + 1;
        tatic[i] = pz;
        if(maxim < dp[i]){
            maxim = dp[i];
            poz = i;
        }
    }
    cout << maxim << '\n';
    reconst(poz);

}