Solução Sequência da Onda

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:

https://gist.github.com/rogerioagjr/e7306bb14afcfffd25df