Cod sursa(job #2717175)

Utilizator TigoanMateiTigoan Matei-Daniel TigoanMatei Data 6 martie 2021 15:55:05
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n;
int v[100005];
int tt[100005], l[100005];
int l_max, k;

int main()
{
    in >> n;
    for(int i = n; i > 0; -- i) in >> v[i];

    for(int i = 1; i <= n; ++ i)
    {
        l[i] = 1;
        tt[i] = i;
        for(int j = i; j > 0; -- j)
        {
            if(v[j] > v[i] && l[j] >= l[i])
            {
                l[i] = l[j] + 1;
                if(l[i] > l_max)
                {
                    l_max = l[i];
                    k = i;
                }
                tt[i] = j;
            }
        }
    }

    out << l_max << '\n';
    while(k != tt[k])
    {
        out << v[k] << " ";
        k = tt[k];
    }
    out << v[k];
    return 0;
}