Cod sursa(job #2577508)

Utilizator georgeconsConstantin George georgecons Data 9 martie 2020 15:39:52
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

void find_scmax(vector<int> &v) {
    vector<int> dp(v.size(), 0);
    vector<int> prec(v.size(), 0);

    dp[0] = 1;
    prec[0] = -1;

    for (int i = 1; i < v.size(); ++i) {
        dp[i] = 1;
        prec[i] = -1;

        int max_length = 0, pos = -1;
        for (int j = i - 1; j >= 0; --j) {
            if (v[i] > v[j] && dp[j] > max_length) {
                max_length = dp[j];
                pos = j;
            }            
        }
        dp[i] = max_length + 1;
        prec[i] = pos;
    }

    int scmax_len = 0, pos;
    for (int i = 0; i < dp.size(); ++i) {
        if (dp[i] > scmax_len) {
            scmax_len = dp[i];
            pos = i;
        }
    }
    out << scmax_len << '\n';


    vector<int> scmax;
    
    while (pos != -1) {
        scmax.push_back(v[pos]);
        pos = prec[pos];
    }
    
    for (int i = scmax_len - 1; i >= 0; --i) {
        out << scmax[i] << " ";
    }
    out << endl;
    
}

int main () {

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

    find_scmax(v);

    return 0;
}