Cod sursa(job #2963609)

Utilizator Sebi_ChiselitaSebastian Chiselita Sebi_Chiselita Data 11 ianuarie 2023 16:32:54
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>

using namespace std;

ifstream in("scmax.in");
ofstream out("scmax.out");
int lung[100001], x[100001];
void refac_subsir (int p, int l, int val)
{
    if(l == 0)
    {
        return;
    }
    if (lung[p] == l && x[p] < val)
    {
        refac_subsir(p - 1, l - 1, x[p]);
        out<<x[p]<<" ";
    }
    else
    {
        refac_subsir(p - 1, l, val);
    }
}

int main()
{
    int pmax = 1, n;
    in >> n;
    for(int i = 1; i <= n; i++)
    {
        int l_j = 0;
        in >> x[i];
        for (int j = 1; j < i; j++)
        {
            if (x[j] < x[i])
            {
                if (lung[j] > l_j)
                {
                    l_j = lung[j];
                }
            }
        }
        lung[i] = 1 + l_j;
        if (lung[i] > lung[pmax])
        {
            pmax = i;
        }
    }
    out << lung[pmax]<<"\n";
    refac_subsir(pmax, lung[pmax], x[pmax] + 1);
    in.close();
    out.close();

    return 0;
}