Cod sursa(job #1717301)

Utilizator Burbon13Burbon13 Burbon13 Data 14 iunie 2016 17:53:33
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>

using namespace std;

const int nmx = 100002;

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

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)
        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;
}