Cod sursa(job #2285276)

Utilizator TooHappyMarchitan Teodor TooHappy Data 18 noiembrie 2018 13:30:36
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream in("scmax.in");
ofstream out("scmax.out");

void showSol(int i, const vector< int > &pre, const vector< int > &v) {
    if(pre[i] == -1) {
        out << v[i] << " ";
        return;
    }

    showSol(pre[i], pre, v);
    out << v[i] << " ";
}

int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);
    
    int n; in >> n;

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

    vector< int > dp(n + 1, 1), pre(n + 1, -1);
    int ans = 1, start = 1;
    for(int i = 2; i <= n; ++i) {
        for(int j = 1; j < i; ++j) {
            if(v[j] < v[i] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                pre[i] = j;
            }

            if(dp[i] > ans) {
                ans = dp[i];
                start = i;
            }
        }
    }

    out << ans << "\n";
    showSol(start, pre, v);

    in.close(); out.close();
 
    return 0;
}