Cod sursa(job #2489940)

Utilizator andreighinea1Ghinea Andrei-Robert andreighinea1 Data 9 noiembrie 2019 13:44:31
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
#define Nmax 100001

using namespace std;

ifstream f("scmax.in");
ofstream o("scmax.out");

int i,j,n,dp[Nmax],v[Nmax],suc[Nmax],smax,m,imax;

int main()
{
    f >> n;
    for(i=1;i<=n;++i)
        f >> v[i];

    for(i=n;i>0;--i){
        m=0;
        for(j=i+1;j<=n;++j){
            if(v[i]<v[j] && m<dp[j]){
                m=dp[j];
                suc[i]=j;
            }
        }
        dp[i]+=m+1;
        if(smax<dp[i]){
            smax=dp[i];
            imax=i;
        }
    }
    o << smax << '\n';
    while(imax){
        o << v[imax] << " ";
        imax=suc[imax];
    }
    return 0;
}