Cod sursa(job #3344489)

Utilizator 1gbr1Gabara 1gbr1 Data 2 martie 2026 10:08:52
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[100005],dp[100005],urm[100005];
int main() {
    int n;
    fin>>n;
    for (int i=1; i<=n; i++)
        fin>>a[i];
    for (int i=n; i>=1; i--) {
        dp[i]=1;
        int maxx=0,pos=n+1;
        for (int j=i+1; j<=n; j++)
            if (a[i]<a[j] and dp[j]>maxx)
                maxx=dp[j],pos=j;
        dp[i]+=maxx;
        urm[i]=pos;
    }
    int maxx=0,start;
    for (int i=1; i<=n; i++)
        if (maxx<dp[i])
            maxx=dp[i],start=i;
    fout<<maxx<<'\n';
    while (start!=n+1) {
        fout<<a[start]<<" ";
        start=urm[start];
    }
    return 0;
}
// 2 0 3 -1 7 -4