Cod sursa(job #1059221)

Utilizator caen1c a e n caen1 Data 16 decembrie 2013 14:01:13
Problema Subsir crescator maximal Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>

#define IN "scmax.in"
#define OUT "scmax.out"
#define NMAX 100000

static unsigned long A[NMAX + 1];
static int S[NMAX + 1], K[NMAX + 1];

void print(int i)
{
    if (S[i]) {
        print(K[i]);
        printf("%ld ", A[i]);
    }
}

int main(void)
{
    int n, i, j, max, M, j_max = 0;

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

    scanf("%d", &n);

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

    M = 0;
    for (i = 1; i <= n; i++) {
        j_max = 0;
        for (j = 1; j < i; j++)
            if (A[i] > A[j] && S[j] > S[j_max])
                j_max = j;
        S[i] = S[j_max] + 1;
        K[i] = j_max;
        if (S[i] > S[M])
            M = i;
    }

    printf("%d\n", S[M]);
    print(M);
    printf("\n");

    return 0;
}