Cod sursa(job #2172812)

Utilizator edynator34Nechitoaia George-Edward edynator34 Data 15 martie 2018 18:04:11
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int best[100005],pre[100005],i,j,n,v[100005];
int ULTIMATUM_L,ULTIMATUM_J;
int main()
{   int lmax,jbest;
    in>>n;
    for(int i=1;i<=n;++i) in>>v[i];
    best[n]=1;
    pre[n]=0;
    for(i=n-1;i>=1;--i){
            lmax=0,jbest=0;
        for (int j=i+1;j<=n;++j){
            if(lmax<best[j] && v[j]>v[i]){
                lmax=best[j];
                jbest=j;
            }
            if(lmax > 0) {
                best[i]=lmax+1;
                pre[i]=jbest;
            }
            else{
                best[i]=1;
                pre[i]=0;
            }
            if(best[i] > ULTIMATUM_L){
                ULTIMATUM_L=best[i];
                ULTIMATUM_J=i;
            }

        }
    }
        out<<ULTIMATUM_L<<'\n';
        do{ out<<v[ULTIMATUM_J]<<' ';
         ULTIMATUM_J=pre[ULTIMATUM_J];
        }while(pre[ULTIMATUM_J] != 0);
        out<<v[ULTIMATUM_J]<<'\n';
    return 0;
}