Cod sursa(job #3294651)

Utilizator adela_codreanCodrean Adela-Maria adela_codrean Data 26 aprilie 2025 18:58:58
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

#define maxi 100000

int a[maxi], L[maxi], v[maxi];
int NextIndex[maxi];

int main()
{
    int n, Lmaxi, pozLmax;
    Lmaxi = -1;
    fin >> n;
    for(int i = 0; i < n; i++)
        fin >> a[i];
    for(int i = n - 1; i >= 0; i --)
    {
        L[i] = 1;
        NextIndex[i] = -1;
        for(int j = i + 1; j < n; j ++)
        {
            if(a[i] < a[j] && L[i] < L[j] + 1)
            {
                L[i] = L[j] + 1;
                NextIndex[i] = j;
            }
        }

    }
    for(int i = 0; i < n; i ++)
    {
        if(L[i] > Lmaxi)
        {
            Lmaxi = L[i];
            pozLmax = i;
        }
    }
    fout << Lmaxi << endl;
    for(int i = pozLmax; i != -1; i = NextIndex[i])
    {
        fout << a[i] << " ";
    }
    return 0;
}