Cod sursa(job #2965062)

Utilizator PingStrpewpewpac PingStr Data 14 ianuarie 2023 13:04:38
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;

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

int a[100003], lg[100003];

int main()
{
    int n;
    fin>>n;
    for (int i = 1; i <= n; i++)
    {
        fin>>a[i];
    }
    lg[n] = 1;
    for (int i = n - 1; i >= 1; i--)
    {
        lg[i] = 1;
        for (int j = i + 1; j <= n; j++)
        {
            if (a[i] < a[j] && lg[i] < lg[j] + 1)
            {
                lg[i] = lg[j] + 1; 
            }
        }
    }
    int max = lg[1];
    for (int i = 2; i <= n; i++)
    {
        if (max <= lg[i])
        {
            max = lg[i];
        }
    }
    int k = 1;
    while (max != lg[k])
    {
        k++;
    }
    int p = k;
    fout<<lg[k]<<'\n';
    fout<<a[p]<<' ';
    max--;
    do
    {
        p++;
        if (lg[p] == lg[k] - 1 && a[p] >= a[k])
        {
            k = p;
            fout<<a[p]<<' ';
            max--;
        }
    } while (max > 0);
    fin.close();
    fout.close();
    return 0;
}