Cod sursa(job #1059148)

Utilizator caen1c a e n caen1 Data 16 decembrie 2013 11:42:33
Problema Subsir crescator maximal Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.84 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] == 0)
        return;

    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]);
        S[i] = 1;
    }

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

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

    return 0;
}