Cod sursa(job #2210722)

Utilizator Raresr14Rosca Rares Raresr14 Data 7 iunie 2018 19:30:31
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int i,j,maxim,n,v[100100],L[100100],T[100100],S[100100],u,poz,k;
int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v[i];
        if(v[i]>maxim)
            maxim=v[i];
    }
    v[++n]=maxim+1;
    L[1]=1;
    for(i=2;i<=n;i++){
        maxim=0;
        for(j=1;j<i;j++)
            if(v[j]<v[i]&&L[j]>maxim){
                maxim=L[j];
                poz=j;
            }
       if(maxim!=0){
            L[i]=1+maxim;
            T[i]=poz;
       }else{
            L[i]=1;
            T[i]=0;
       }
    }
    u=n;
    while(u!=0){
        S[++k]=v[u];
        u=T[u];
    }
    fout<<k-1<<"\n";
    for(i=k;i>=2;i--)
        fout<<S[i]<<" ";
    return 0;
}