Cod sursa(job #2963591)

Utilizator karina_antoniuAntoniu Karina karina_antoniu Data 11 ianuarie 2023 16:10:50
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
using namespace std;

ifstream cin("scmax.in");
ofstream cout("scmax.out");

const int N = 1e5;
int n, a[N + 1], lung[N + 1], pmax;

void refac_subsir(int p, int l, int val)
{
    if(l == 0)
        return;
    if(lung[p] == l && a[p] < val)
    {
        refac_subsir(p - 1, l - 1, a[p]);
        cout << a[p] << " ";
    }
    else
        refac_subsir(p - 1, l, val);
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
    {
        int l_j = 0;
        for(int j = 1; j < i; j++)
        {
            if(a[j] < a[i])
                if(lung[j] > l_j)
                    l_j = lung[j];
        }
        lung[i] = 1 + l_j;
        if(lung[i] > lung[pmax])
            pmax = i;
    }
    cout << lung[pmax] << endl;
    refac_subsir(pmax, lung[pmax], a[pmax] + 1);
    cin.close();
    cout.close();
    return 0;
}