Cod sursa(job #3356067)

Utilizator Belea_DariusBelea Mihai Darius Belea_Darius Data 29 mai 2026 14:33:52
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>
#define MAXN 100000

using namespace std;

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

int v[MAXN + 1], dp[MAXN + 1], to[MAXN + 1];

int main()
{
    int n, i, j, mx, pos;

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

    mx = -1;
    for(i = n; i >= 1; i--){
        dp[i] = 1;
        to[i] = -1;
        for(j = i + 1; j <= n; j++){
            if(v[j] > v[i]){
                if(dp[j] + 1 > dp[i]){
                    dp[i] = dp[j] + 1;
                    to[i] = j;
                }
            }
        }
        if(dp[i] > mx){
            mx = dp[i];
            pos = i;
        }
    }
    fout << mx << "\n";
    while(pos != -1){
        fout << v[pos] << " ";
        pos = to[pos];
    }
    return 0;
}