Cod sursa(job #552311)

Utilizator gerrGabriel Erzse gerr Data 12 martie 2011 08:45:12
Problema Subsir crescator maximal Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 0.96 kb
/* Infoarena SCMAX (Subsir crescator maximal) http://infoarena.ro */
#include <stdio.h>

#define SIZE 110000

int n, a[SIZE];
int len[SIZE], t[SIZE];

void afis(int i)
{
    if (i >= 0) {
        afis(t[i]);
        printf("%d ", a[i]);
    }
}

int main(void)
{
    int i, j, max, jmax;

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

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

    len[0] = 1;
    t[0] = -1;
    for (i = 1; i < n; i++) {
        max = 0;
        jmax = -1;
        for (j = 0; j < i; j++) {
            if (a[j] < a[i] && max < len[j]) {
                max = len[j];
                jmax = j;
            }
        }
        len[i] = max + 1;
        t[i] = jmax;
    }

    max = len[0];
    jmax = 0;
    for (j = 1; j < n; j++) {
        if (max < len[j]) {
            max = len[j];
            jmax = j;
        }
    }
    printf("%d\n", max);
    afis(jmax);
    printf("\n");

    return 0;
}