Cod sursa(job #3348024)

Utilizator AlexandruNNNAlexandru Nicolita AlexandruNNN Data 19 martie 2026 11:42:04
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000

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

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

stack<int> st;

int main(){
    int n,i,j,poz,mx,ind;

    fin >> n;

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

    mx = 0;
    poz = 1;
    for (i = 2; i <= n; i ++){
        for (j = 1; j <= i - 1; j ++){
            if (v[j] < v[i] && dp[j] + 1 > dp[i])
                dp[i] = dp[j] + 1;
        }

        if (dp[i] > mx){
            mx = dp[i];
            poz = i;
        }
    }

    ind = poz;
    st.push(v[poz]);
    for (i = poz - 1; i >= 1; i --){
        if (dp[i] == dp[ind] - 1 && v[i] < v[ind]){
            st.push(v[i]);
            ind = i;
        }
    }

    fout << st.size() << '\n';

    while (!st.empty()){
        fout << st.top() << ' ';
        st.pop();
    }

    fin.close();
    fout.close();

    return 0;
}