Cod sursa(job #698775)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 29 februarie 2012 15:56:42
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <iostream>
using namespace std;

struct dinamica {
    int l;
    int r;
};
dinamica d[100005];

int n, v[100005], maxim, sol[100005];

int main()
{
    int i, j;
    freopen ("scmax.in", "r", stdin);
    freopen ("scmax.out", "w", stdout);
    scanf("%d", &n);
    d[0].l = 1;
    d[0].r = 0;
    d[1].l = 1;
    d[1].r = 0;
    scanf("%d", &v[1]);
    for(i = 2; i <= n; ++i) {
        scanf("%d", &v[i]);
        maxim = 0;
        for(j = 1; j < i; ++j) {
            if(v[i] > v[j] && d[j].l >= d[maxim].l)
                maxim = j;
        }
        d[i].l = d[maxim].l + 1;
        d[i].r = maxim;
    }
    maxim = -1;
    for(i = 1; i <= n; ++i)
        if(d[i].l > d[maxim].l)
            maxim = i;
    printf("%d\n", d[maxim].l - 1);
    sol[++sol[0]] = v[maxim];
    while(d[maxim].r > 0) {
        sol[++sol[0]] = v[d[maxim].r];
        maxim = d[maxim].r;
    }
    for(i = sol[0]; i >= 1; --i)
        printf("%d ", sol[i]);
    return 0;
}