Cod sursa(job #2867898)

Utilizator VDAVIDVladuca david VDAVID Data 10 martie 2022 16:57:20
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;

int n, v[100001], best[100001], poz[100001];

int main() {
    ifstream cin("scmax.in");
    ofstream cout("scmax.out");
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> v[i];

    best[n] = 1;
    poz[n] = -1;
    int nmax = 0, ult = 0;
    for(int i = n - 1; i >= 1; i--) {
        best[i] = 1;
        poz[n] = -1;
        for(int j = i + 1; j <= n; j++) {
            if(v[i] < v[j] && best[i] < best[j] + 1) {
                best[i] = best[j] + 1;
                poz[i] = j;
                if(nmax < best[i])
                    nmax = best[i], ult = i;
            }
        }
    }
    cout << nmax << endl;
    while(ult != -1) {
        cout << v[ult] << ' ';
        ult = poz[ult];
    }
    return 0;
}