Cod sursa(job #3160426)

Utilizator ScipexRobert Chiri Scipex Data 23 octombrie 2023 22:43:00
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;

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

int n;
int a[100000];
int idx[100000], l[100000], lmax, imx;

int main() {
    fin >> n;
    for (int i = 0; i < n; i++) {
        fin >> a[i];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[i] > a[j]) {
                if (l[j] + 1 > l[i]) {
                    l[i] = l[j] + 1;
                    idx[i] = j;
                }
            }
        }

        if (lmax < l[i]) {
            lmax = l[i];
            imx = i;
        }
    }

    fout << lmax + 1 << "\n";
    vector<int> v(lmax + 1);
    for (int i = lmax; i >= 0; i--) {
        v[i] = a[imx];
        imx = idx[imx];
    }
    for (int x : v) {
        fout << x << " ";
    }
}