Cod sursa(job #3210409)

Utilizator racoltaRacolta Victor racolta Data 6 martie 2024 10:42:41
Problema Subsir crescator maximal Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 100001;

int v[NMAX];
int lmax[NMAX];
int n,lm,pozmax,next_i;
int nexti[NMAX];
int scmax(int k){
    if(lmax[k] != -1)
    {
        return lmax[k];
    }

    int best_lmax = 1;
    for(int i = k + 1; i <= n; i++)
    {
        if(v[i] > v[k])
        {
            int lmax_from_i = scmax(i);
            if(lmax_from_i + 1 > best_lmax)
            {
                best_lmax = lmax_from_i + 1;

                if(lmax[i]>lm)
                {
                    lm=lmax[i];
                    next_i=i;
                }
            }
        }
    }
    nexti[k]=next_i;
    lmax[k] = best_lmax;
    return lmax[k];
}




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

    int best = 1;
    for(int i = 1; i <= n; i++){
        int lmax_for_i = scmax(i);
        if(lmax_for_i > best){
            best = lmax_for_i;
            pozmax=i;
        }
    }
    g << best << "\n";
    int cur=pozmax;
    while(cur!=0)
    {
        g << v[cur] << " ";
        cur=nexti[cur];
    }


    return 0;
}