Cod sursa(job #2972308)

Utilizator gripzStroescu Matei Alexandru gripz Data 29 ianuarie 2023 01:19:34
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <vector>

#define MAXN 100003

using namespace std;

int N, a[MAXN], d[MAXN], pre[MAXN];

int main()
{
    cin >> N;
    for(int i = 1; i <= N; i++) {
        cin >> a[i];

    }

    d[1] = 1;
    pre[1] = -1;
    for(int i = 2; i <= N; i++) {
        int besti_val = 0, besti = -1;
        for(int j = 1; j < i; j++) {
            if(a[j] < a[i]) {
                if(besti_val < d[j]) {
                    besti_val = d[j];
                    besti = j;
                }
            }
        }
        d[i] = besti_val + 1;
        pre[i] = besti;
    }



    int imax = 1, maxval = 0;
    for(int i = 1; i <= N; i++) {
        if(d[i] > maxval) {
            maxval = d[i];
            imax = i;
        }
    }
    cout << d[imax] << endl;

    int i = imax;
    vector<int> R;
    while(i != -1){
        R.push_back(a[i]);
        i = pre[i];
    }

    for(auto it = R.rbegin(); it != R.rend(); it++) {
        cout << *it << " ";
    }

    return 0;
}