Cod sursa(job #2962205)

Utilizator TheAndreiEnache Andrei Alexandru TheAndrei Data 7 ianuarie 2023 23:26:39
Problema Subsir crescator maximal Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>

using namespace std;

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

#define NMAX 10003

int v[NMAX], best[NMAX], poz[NMAX], p;

int main()
{
    int n, max;
    fin>>n;
    for(int i=1;i<n;i++){
        fin>>v[i];
    }

    best[n]=1;
    poz[n]=-1;
    max=1;
    p=n;

    for(int i=n-1;i>=1;--i)
    {
       best[i]=1;
       poz[i]=-1;
       for(int j=i+1;j<=n;++j)
           if(v[i]<v[j] && best[i]<best[j]+1)
             {
             best[i]=best[j]+1;
             poz[i]=j;
             if(best[i]>max) max=best[i];
             p=i;
             }
    }

    fout<<max<<"\n";

    while(p!=-1){
        fout<<v[p]<<" ";
        p=poz[p];
    }
    return 0;
}