Cod sursa(job #3292374)

Utilizator IleaIlea Bogdan Ilea Data 8 aprilie 2025 10:31:49
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 100001

int n, a[NMAX], dp[NMAX];
int from[NMAX];
vector<int> sol;
void solve(){
    cin>>n;
    for (int i=1; i<=n; ++i){
        cin>>a[n-i+1];
    }
    dp[1]=1;
    int imax=1;
    for (int i=2; i<=n; ++i){
        //if (a[i]%2)continue;
        dp[i]=1;
        for (int j=1; j<i; ++j){
            //if (a[j]%2)continue;
            if (a[j]>a[i]){
                if (dp[i]<dp[j]+1){
                    from[i]=j;
                    dp[i]=dp[j]+1;
                }
            }
        }
        if (dp[imax]<dp[i])imax=i;
    }
    //for (int i=1; i<=n; ++i)cout<<dp[i]<<" ";cout<<endl;
    cout<<dp[imax]<<"\n";
    while (imax){
        cout<<a[imax]<<" ";
        imax=from[imax];
    }
}
int main(){
    #ifdef LOCAL
        freopen("date.in", "r", stdin);
    #else
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    #endif
    solve();
    return 0;
}