Cod sursa(job #2759150)

Utilizator rapidu36Victor Manz rapidu36 Data 15 iunie 2021 18:34:02
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>

using namespace std;

const int N = 1e5;

int a[N], l[N], sol[N];


int main()
{
    ifstream in("scmax.in");
    ofstream out("scmax.out");
    int n, pmax = 0;
    in >> n;
    for (int i = 0; i < n; i++)
    {
        in >> a[i];
        l[i] = 1;///l[i] = lungimea max a unui subsir strict cresc. care se termina cu a[i]
        for (int j = 0; j < i; j++)
        {
            if (a[j] < a[i])///putem sa-l adaugam pe a[i] la un subsir care se termina cu a[j]
            {
                l[i] = max(l[i], 1 + l[j]);
            }
        }
        if (l[i] > l[pmax])
        {
            pmax = i;
        }
    }
    out << l[pmax] << "\n";
    int vf = 0;
    sol[vf++] = a[pmax];
    for (int i = pmax; i >= 0; i--)
    {
        if (a[i] < a[pmax] && l[i] == l[pmax] - 1)
        {
            pmax = i;
            sol[vf++] = a[pmax];
        }
    }
    for (int i = vf - 1; i >= 0; i--)
    {
        out << sol[i] << " ";
    }
    in.close();
    out.close();
    return 0;
}