Cod sursa(job #2050554)

Utilizator theodor.vladTheodor Vlad theodor.vlad Data 28 octombrie 2017 10:25:27
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#define maxim(a, b) a > b ? a : b

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

void citire();
void dinamica();

int n;
int v[100005], lg[100005];

int main()
{
    citire();
    dinamica();
    return 0;
}

void dinamica()
{
    int maxx = 1, pozmax = n;
    lg[n] = 1;

    for (int i = n - 1; i; i--)
        for (int j = i + 1; j <= n; j++)
        {
            if (v[i] < v[j])
            {
                lg[i] = maxim(1 + lg[j], lg[i]);

                if (lg[i] > maxx)
                {
                    maxx = lg[i];
                    pozmax = i;
                }
            }
            else
            {
                lg[i] = 1;
            }
        }


    fout << maxx << '\n';
    for (int i = pozmax; i <= n && maxx; i++)
        if (lg[i] == maxx)
        {
            maxx--;
            fout << v[i] << ' ';
        }
}

void citire()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i];
}