Cod sursa(job #3174389)

Utilizator AlexMotoascaMotoasca Alexandru AlexMotoasca Data 24 noiembrie 2023 18:35:36
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>

using namespace std;

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

int n;
int A[100001];
int LG[100001];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    LG[n] = 1;
    for (int i = n - 1; i > 0; i--) {
        LG[i] = 1;
        for (int j = i + 1; j <= n; ++j)
            if (A[i] < A[j] && LG[i] < LG[j] + 1)
                LG[i] = LG[j] + 1;
    }
    int pmax = 1;
    for (int i = 2; i <= n; i++)
        if (LG[i] > LG[pmax])
            pmax = i;
    cout << LG[pmax] << "\n";
    int p = pmax;
    do {
        cout << A[p] << " ";
        int pUrm = p + 1;
        while (pUrm <= n && !(A[pUrm] >= A[p] && LG[pUrm] == LG[p] - 1))
            pUrm++;
        if (pUrm <= n)
            p = pUrm;
        else
            p = -1;
    } while (p != -1);
    return 0;
}