Cod sursa(job #2050627)

Utilizator theodor.vladTheodor Vlad theodor.vlad Data 28 octombrie 2017 10:43:09
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 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--)
    {
        lg[i] = 1;
        for (int j = i + 1; j <= n; j++)
        {
            if (v[i] < v[j] && lg[i] < lg[j] + 1)
            {
                lg[i] = lg[j] + 1;
                if (lg[i] > maxx)
                {
                    maxx = lg[i];
                    pozmax = i;
                }
            }
        }
    }


    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];
}