Cod sursa(job #2266396)

Utilizator Opariuc_RaresOpariuc Rares Ioan Opariuc_Rares Data 22 octombrie 2018 17:11:41
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#define NMAX 100002
using namespace std;

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

int n, v[NMAX], lis[NMAX], urm[NMAX];

void citire();
void pd();
void afisare();

int main()
{
    citire();
    pd();
    return 0;
}
void citire()
{
    int i;
    fin >> n;
    for (i = 0; i < n; i++)
        fin >> v[i];
    lis[n - 1] = 1;
}
void pd()
{
    int i, j, copie = 1, maxim = -1, pozmax;
    for (i = n - 1; i >= 0; i--)
    {
        for (j = i; j < n; j++)
        {
            if (v[i] < v[j] && lis[j] >= lis[i])
            {
                lis[i] = lis[j] + 1;
                urm[i] = j;

            }
        }
        if (lis[i] == 0)
            lis[i] = 1;
        if (lis[i] > maxim)
        {
            maxim = lis[i];
            pozmax = i;
        }
    }
    fout << maxim << '\n';
    fout << v[pozmax] << ' ';
    while (urm[pozmax])
    {
        fout << v[urm[pozmax]]  << ' ';
        pozmax = urm[pozmax];
    }
}