Cod sursa(job #2685462)

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

#define NMax 100001

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.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;
    for(int i = 2; i <= N; i++)
    {
        f >> Sir[i];
        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;
}