Mai intai trebuie sa te autentifici.

Cod sursa(job #2261346)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 16 octombrie 2018 10:24:54
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#define NMAX 100010

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

int n;
int a[NMAX];

int lis[NMAX];
int prec[NMAX];

int main() {
    int i, j;
    int lisMax, posMax;

    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];

    lisMax = -1;
    for (i = n; i >= 1; i--) {
        lis[i] = 1;
        prec[i] = 0;

        for (j = i + 1; j <= n; j++)
            if (a[i] < a[j] && lis[j] + 1 > lis[i]) {
                lis[i] = lis[j] + 1;
                prec[i] = j;
            }

        if (lis[i] > lisMax) {
            lisMax = lis[i];
            posMax = i;
        }
    }

    fout << lisMax << '\n';
    for (i = posMax; i <= n && lisMax; i++)
        if (lis[i] == lisMax) {
            lisMax--;
            fout << a[i] << ' ';
        }

    fout.close();
    return 0;
}