Cod sursa(job #3320582)

Utilizator alexiabortunBortun Alexia alexiabortun Data 6 noiembrie 2025 16:15:59
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");
#define N 100005
int n, a[N], lg[N], T[N];

void citire()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> a[i];
}
void sclm()
{
    for(int i = 1; i <= n; i++)
    {
        lg[i] = 1;
        T[i] = 0;
        for(int j = 1; j < i; j++)
            if(a[j] < a[i] && lg[j] + 1 > lg[i])
            {
                lg[i] = lg[j] + 1;
                T[i] = j;
            }
    }
}
void drum(int i)
{
    if(T[i])
    {
        drum(T[i]);
        fout << a[i] << " ";
    }
    else fout << a[i] << " ";
}
int main()
{
    citire();
    sclm();
    int lgmax = -1, poz = -1;
    for(int i = 1; i <= n; i++)
        if(lg[i] > lgmax)
        {
            lgmax = lg[i];
            poz = i;
        }
    fout << lgmax << "\n";
    drum(poz);
    return 0;
}