Cod sursa(job #861893)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 21 ianuarie 2013 23:19:39
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Siruri-1 Marime 0.89 kb
#include <cstdio>

int n, lungime;
int v[100001];
int L[100001];

void citire();
void dinamica();
void afis();

int main(){

    citire();
    dinamica();
    afis();

    return 0;
}

void citire(){

    freopen("scmax.in", "r", stdin);

    scanf("%d", &n);

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

void dinamica(){

    int maxim = 0;

    L[n] = 1;

    for(int i = n - 1; i >= 1; i--){

        maxim = 0;

        for(int j = i + 1; j <= n; j++)
            if(L[j] > maxim && v[i] < v[j])
                maxim = L[j];

        L[i] = maxim + 1;

        if(lungime < L[i])
            lungime = L[i];
    }
}

void afis(){

    freopen("scmax.out", "w", stdout);

    printf("%d\n", lungime);

    int t = 0, p = 1;

    do{

        while(L[p] != lungime || v[t] > v[p])
            p++;

        printf("%d ", v[p]);

        t = p;
        lungime--;

    }while(lungime);
}