Cod sursa(job #2364977)

Utilizator Cristian25Cristian Stanciu Cristian25 Data 4 martie 2019 11:37:47
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda pregatire_cls12_oji Marime 0.84 kb
#include <bits/stdc++.h>
#define len 100000

using namespace std;

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

deque<unsigned> sol;

unsigned N, lmax, v[len], scmax[len];

int main()
{
    in >> N;
    for(unsigned i = 0; i < N; ++i)
    {
        in >> v[i];
        scmax[i] = 1;
        for(unsigned j = 0; j < i; ++j)
            if(v[j] < v[i])
            {
                scmax[i] = max(scmax[i], scmax[j] + 1);
                lmax = max(lmax, scmax[i]);
            }
    }
    out << lmax << '\n';
    for(int i = N - 1; i >= 0; --i)
    {
        if(scmax[i] == lmax)
        {
            sol.push_front(v[i]);
            --lmax;
        }
        if(!lmax)
            break;
    }
    while(!sol.empty())
    {
        out << *sol.begin() << ' ';
        sol.pop_front();
    }
    return 0;
}