Cod sursa(job #698816)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 29 februarie 2012 16:12:43
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <iostream>
using namespace std;

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

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

int main()
{
    int i, j;
    freopen ("scmax.in", "r", stdin);
    freopen ("scmax.out", "w", stdout);
    scanf("%d", &n);
    d[0].l = 0;
    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;
        if(d[i].l > d[maxsol].l)
            maxsol = i;
    }
    for(i = 1; i <= n; ++i)
        cerr << d[i].l << ' ' << d[i].r << "\n";
    printf("%d\n", d[maxsol].l);
    sol[++sol[0]] = v[maxsol];
    do {
        sol[++sol[0]] = v[d[maxsol].r];
        maxsol = d[maxsol].r;
    }while(d[maxsol].r > 0);
    for(i = sol[0]; i >= 1; --i)
        printf("%d ", sol[i]);
    return 0;
}