Cod sursa(job #2762861)

Utilizator StasBrega Stanislav Stas Data 9 iulie 2021 18:15:50
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

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

int main() {
    
    int n; fin >> n;
    vector<int> a(n);
    
    for(int &x: a)
        fin >> x;
        
    int ans_v = 1, last_prev = -1;
    vector<int> dp(n, 1);
    vector<int> prev(n, -1);
    
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < i; ++j)
            if(a[i] > a[j] and dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
                if(dp[i] > ans_v)
                    ans_v = dp[i],
                    last_prev = i;
            }
    
    fout << ans_v << '\n';
    
    vector<int> ans(ans_v);
    while(last_prev != -1)
        ans[--ans_v] = a[last_prev],
        last_prev = prev[last_prev];
        
    for(int x: ans)
        fout << x << ' ';
    
    return 0;

}