Cod sursa(job #2489948)

Utilizator MariusblockMoga Marius-Ioan Mariusblock Data 9 noiembrie 2019 13:59:01
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
using namespace std;

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

int DP[100005];
int x[100005];
int succ[100005];

int main()
{
    int n,i,j,maxDPj = 0,sol = 0,poz = 0;
    fin>>n;
    for(i = 1; i <= n; i++){
        fin>>x[i];
    }
    for(i = n; i >= 1; --i){
        maxDPj = 0;
        for(j = i+1; j <= n; j++){
            if(x[i] < x[j]){
                if(maxDPj < DP[j]){
                    maxDPj = DP[j];
                    succ[i] = j;
                }
            }
        }
        DP[i] = 1 + maxDPj;
    }
    for(i = 1; i <= n; i++){
        if(sol < DP[i]){
            sol = DP[i];
            poz = i;
        }
    }
    fout<<sol<<endl;
    while(poz){
        fout<<x[poz]<<" ";
        poz = succ[poz];
    }
    return 0;
}