Cod sursa(job #2759137)

Utilizator CaptnBananaPetcu Tudor CaptnBanana Data 15 iunie 2021 17:32:06
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

const int N = 1e5 + 1;
int n, v[N], dp[N], maxval, ifin, ans[N], aux;

int main(){
    f >> n;
    for(int i = 0; i < n; i++)
        f >> v[i];

    f.close();
    dp[0] = 1;
    for(int i = 1; i < n; i++){
        dp[i] = 1;
        for(int j = 0; j < i; j++){
            if(v[j] < v[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }

    for(int i = 1; i < n; i++){
        if(dp[i] > maxval){
            maxval = dp[i];
            ifin = i;
        }
    }

    g << maxval << '\n';
    aux = maxval;
    ans[aux--] = v[ifin];
    for(int i = ifin - 1; i >= 0; i--){
        if(dp[i] == aux)
            ans[aux--] = v[i];
    }

    for(int i = 1; i <= maxval; i++)
        g << ans[i] << ' ';

    g.close();
}