Cod sursa(job #1657744)

Utilizator user_namePopa Emil user_name Data 20 martie 2016 19:25:42
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <cstdio>
using namespace std;

const int NMAX = 100003;
int best[NMAX], a[NMAX], poz[NMAX];
int _max, p, n;

void read()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
}

void dinamica()
{
    int i, j;
    best[n] = 1;
    poz[n] = -1;
    _max = 1; p = n;

    for (i = n - 1; i >= 1; --i){
        best[i] = 1;
        poz[i] = -1;
        for (j = i + 1; j <= n; ++j)
        if (a[i] < a[j] && best[i] < best[j] + 1){
            best[i] = best[j] + 1;
            poz[i] = j;
            if (best[i] > _max)
                _max = best[i], p = i;
        }
    }
}

void constr()
{
    int i = p;
    while (i != -1){
        printf("%d ", a[i]);
        i = poz[i];
    }
}

int main()
{
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);

    read();
    dinamica();
    printf("%d\n", _max);
    constr();

    return 0;
}