Cod sursa(job #3210402)

Utilizator AlexDudescuDudescu Alexandru AlexDudescu Data 6 martie 2024 10:19:11
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>

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

const int NMAX = 100005;
int n,v[NMAX],lm[NMAX];
int next_elem[NMAX];

int scm(int m)
{
    if(lm[m]!=-1)
    {
        return lm[m];
    }
    int best_lmax = 1;
    next_elem[m] = -1;
    for(int i=m;i<=n;i++)
    {
        if(v[i]>v[m])
        {
            int lmax_from_i = scm(i);
            if (lmax_from_i + 1 > best_lmax) {
                best_lmax = lmax_from_i + 1;
                next_elem[m] = i;
            }

        }
    }
    lm[m] = best_lmax;
    return lm[m];
}

int main()
{
    int maxx = -1, elem_lmax  = 0, index;
    fin >> n;
    for(int i=1;i<=n;i++)
    {
        fin >> v[i];
        lm[i]=-1;
    }
    for (int i = 1; i <= n; i++) {
        int lmax = scm(i);
        if (lmax > maxx) {
            maxx = lmax;
            elem_lmax = i;
        }
    }

    fout << maxx << "\n";

    index = elem_lmax;
    while(index != -1) {
        fout << v[index] << " ";
        index = next_elem[index];
    }

    return 0;
}