Cod sursa(job #669416)

Utilizator caen1c a e n caen1 Data 26 ianuarie 2012 22:12:30
Problema Subsir crescator maximal Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>

#define IN "scmax.in"
#define OUT "scmax.out"
#define N 100005

int v[N];

void scmax(int);

int main(void) {

    int n, i;

    freopen(IN, "r", stdin); freopen(OUT, "w", stdout);

    scanf("%d", &n);

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

    scmax(n);

    return 0;
}

void scmax(int n) {

    int L_max[N], urm[N], i, j, l_max, p_max;

    L_max[n] = 1, urm[n] = 0;
    for(i = 1; i <= n; ++i)
        L_max[i] = 1;

    for(i = n - 1; i > 0; --i)
        for(j = i + 1; j <= n; ++j)
            if(L_max[j] + 1 > L_max[i] && v[i] < v[j]) {

                L_max[i] = L_max[j] + 1, urm[i] = j;

                if(L_max[i] > l_max)
                    l_max = L_max[i], p_max = i;
            }

    printf("%d\n", l_max);
    for(i = p_max; i; i = urm[i])
        printf("%d ", v[i]);
    printf("\n");
}