Cod sursa(job #3174378)

Utilizator AlexDavid26Alex Bleotu AlexDavid26 Data 24 noiembrie 2023 18:26:06
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n, arr[100005];
int dp[100005];

void los() {
    int maxim = -1;

    for (int i = n; i > 0; i--) {
        dp[i] = 1;
        for (int j = i + 1; j <= n; j++)
            if (arr[i] < arr[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
                maxim = max(maxim, dp[i]);
            }
    }

    fout << maxim << "\n";

    for (int i = 1; i <= n; i++)
        if (dp[i] == maxim) {
            fout << arr[i] << " ";
            maxim--;
        }
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> arr[i];

    los();
}