Cod sursa(job #2890125)

Utilizator AndreiPaval03Andrei Paval AndreiPaval03 Data 14 aprilie 2022 17:17:40
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>

using namespace std;

int main() {
    ifstream cin("scmax.in");
    ofstream cout("scmax.out");

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

    int lis_max_index = 1;
    int next[n + 1] = {0};  
    int lis[n + 1] = {0};

    lis[n] = 1;
    next[n] = n;
    for (int i = n - 1; i >= 1; --i) {
        int max_index = i;
        for (int j = i + 1; j <= n; j++) {
            if (lis[j] > lis[max_index] and v[j] > v[i]) {
                max_index = j;
            }
        }
        lis[i] = lis[max_index] + 1;
        next[i] = max_index;

        if (lis[i] > lis[lis_max_index]) {
            lis_max_index = i;
        }
    }

    cout << lis[lis_max_index] << endl;
    int i = lis_max_index;
    while (i != next[i]) {
        cout << v[i] << " ";
        i = next[i];
    }
    cout << v[i] << endl;

    return 0;
}