Cod sursa(job #2705971)

Utilizator divadddDavid Curca divaddd Data 13 februarie 2021 16:33:14
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#define MAX 100002
using namespace std;
int n,v[MAX],dp[MAX],tata[MAX],rez[MAX];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
    }
    dp[1] = 1;
    int maxi = 0,poz = 0;
    for(int i = 2; i <= n; i++){
        /// determin dp[i];
        dp[i] = 1;
        for(int j = i-1; j >= 1; j--){
            if(v[j] < v[i] && dp[j]+1 > dp[i]){
                dp[i] = dp[j]+1;
                tata[i] = j;
                if(maxi < dp[i]){
                    maxi = dp[i];
                    poz = i;
                }
            }
        }
    }
    cout << maxi << "\n";
    for(int i = maxi; i >= 1; i--){
        rez[i] = v[poz];
        poz = tata[poz];
    }
    for(int i = 1; i <= maxi; i++){
        cout << rez[i] << " ";
    }
    return 0;
}