Cod sursa(job #2685458)

Utilizator XeinIonel-Alexandru Culea Xein Data 16 decembrie 2020 23:51:24
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>

#define NMax 100001

using namespace std;

ifstream f("in.in");
ofstream g("out.out");
int N, Sir[NMax], Lmax[NMax], Prev[NMax], MAX = 1, I = 1;

void afis_subsir(int i)
{
    if(Prev[i] != 0)
        afis_subsir(Prev[i]);
    g << Sir[i] << ' ';
}

int main()
{
    f >> N;
    f >> Sir[1];
    Lmax[1] = 1;
    Prev[1] = 0;
    for(int i = 2; i <= N; i++)
    {
        f >> Sir[i];
        Prev[i] = 0;
        for(int j = 1; j < i; j++)
            if(Sir[j] < Sir[i] && Lmax[j] > Lmax[i])
            {
                Lmax[i] = Lmax[j];
                Prev[i] = j;
            }
        Lmax[i]++;
        if(Lmax[i] > MAX)
        {
            MAX = Lmax[i];
            I = i;
        }
    }
    g << MAX << '\n';
    afis_subsir(I);
    return 0;
}