Cod sursa(job #3182568)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 9 decembrie 2023 10:19:11
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <algorithm>

using namespace std;
int dp[100005];
int v [100005];
int succ[100005];
/*
Subproblema: cel mai lung subsir
crescator maximal care incepe cu pozitia i.
*/
int main()
{
    cin.tie(0); cin.sync_with_stdio(false);
    cout.tie(0); cout.sync_with_stdio(false);
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);
    int n, elem;
    cin>>n;
    for (int i=1; i<=n; i++) cin>>v[i];
    for (int i=n; i>=1; i--) {
        dp[i]=0;
        for (int j=i+1; j<=n; j++) {
            if (v[j]>v[i]&&dp[j]>dp[i]) {
                dp[i]=dp[j];
                succ[i]=j;
            }
        }
        dp[i]++;
    }
    int maxi=-1, poz=0;
    for (int i=1; i<=n; i++) {
        if (dp[i]>maxi) {
            maxi=dp[i];
            poz=i;
        }
    }
    cout<<maxi<<'\n';
    while (succ[poz]!=0) {
        cout<<v[poz]<<' ';
        poz=succ[poz];
    }
    cout<<v[poz]<<' ';
    return 0;
}