Cod sursa(job #2909521)

Utilizator Dragos1226Dragos Chileban Dragos1226 Data 14 iunie 2022 02:17:59
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");

const int nmax = 1e5;
int n, arr[nmax+5], dp[nmax+5], Next[nmax+5];
int m, imax;

void Solve() {
    for(int i = n; i > 0; i--) {
        for(int j = n; j > i; j--)
            if(arr[j] > arr[i] && dp[j] > dp[i])
                dp[i] = dp[j] , Next[i] = j;

        dp[i]++;

        if(dp[i] > m)
            m = dp[i], imax = i;
    }
    out << m << '\n';
    while(imax) {
        out << arr[imax] << " ";
        imax = Next[imax];
    }
}

int main() {
    in >> n;
    for(int i = 1; i <= n; i++)
        in >> arr[i];
    Solve();
    return 0;
}