Cod sursa(job #1043276)

Utilizator caliuxSegarceanu Calin caliux Data 28 noiembrie 2013 11:11:27
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <stdio.h>
#define NMAX 100002
using namespace std;

int vec[NMAX], urm[NMAX], Lmax[NMAX], m, u, N, i, j, max_vec, poz_vec;

void dinamica(){
    Lmax[N] = 1; urm[N] = 0;
    for(i = N - 1; i >= 1; i--){
        m = 0; u = i;
        for(j = i + 1; j <= N; j++){
            if(vec[i] < vec[j]){
                if(m < Lmax[j]){
                    m = Lmax[j];
                    u = j;
                }
            }
        }
        Lmax[i] = m + 1;
        urm[i] = u;
        if(m + 1 > max_vec){
            max_vec = m + 1;
            poz_vec = i;
        }
    }
}

void drum(){
    printf("%d\n", max_vec);
    while(urm[poz_vec] != 0){
        printf("%d ", vec[poz_vec]);
        poz_vec = urm[poz_vec];
    }
    printf("%d ", vec[poz_vec]);
}

int main(){

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

    scanf("%d", &N);
    for(i = 1; i <= N; i++){
        scanf("%d", &vec[i]);
    }
    dinamica();
    drum();
}