Cod sursa(job #1717310)

Utilizator Burbon13Burbon13 Burbon13 Data 14 iunie 2016 18:04:25
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>

using namespace std;

const int nmx = 100002;

int n;
int a[nmx],l[nmx],ant[nmx], pm = -1, vm = -1;

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

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

    l[n] = 1;
    for(int i = n - 1; i; --i) {
        l[i] = 1;
        for(int j = i + 1; j <= n; ++j)
            if(a[i] < a[j] && l[i] <= l[j] + 1) {
                l[i] = l[j] + 1;
                ant[i] = j;
                if(l[i] > vm) {
                    vm = l[i];
                    pm = i;
                }
            }
    }

    printf("%d\n", l[pm]);
    while(pm) {
        printf("%d ", a[pm]);
        pm = ant[pm];
    }

    return 0;
}