Solução Sequência da Onda

0 Flares Facebook 0 0 Flares ×

Código de Roger Benet, comentários de Rogério Júnior

Para ver o problema original, clique aqui. Esta é uma questão muito simples de LIS (Maior Subsequência Crescente). Se você não conhece este algoritmo, clique aqui para ver a Aula de LIS do Curso Noic. Quando estamos fazendo o algoritmo da LIS, o número da pilha em que colocamos o elemento que estamos processando é exatamente o tamanho da maior subsequência crescente que termina exatamente nele, logo podemos usar o algoritmo da LIS para sabermos a maior sequência crescente que termina em cada elemento e depois fazemos o algoritmo de traz para frente para encontrarmos a maior subsequência decrescente que começa em cada elemento.

Supondo agora que sabemos, para um dado elemento na posição i da sequência, o tamanho da maior subsequência crescente que termina nele (digamos cresc_i) e da maior subsequência decrescente que começa nele (digamos decres_i), a maior Sequência da Onda que podemos criar tendo i como elemento central é justamente usando todos os elementos de min(cresc_i, \ decresc_i) e o maior número de elementos possível de max(cresc_i, \ decresc_i) (que é exatamente min(cresc_i, \ decresc_i)), lembrando de subtrair 1 porque contamos o elemento i duas vezes (o fim da crescente e o começo da decrescente).

Deste modo, a maior Sequência da Onda que tenha i como elemento central terá 2 \times min(cresc_i, \ decresc_i)-1 elementos. Basta calcularmos este valor para todos os valores de i de 1 a n e imprimirmos o maior. Segue o código para melhor entendimento:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: