Introducción a la Programación Dinámica - Nivel Avanzado

El día de ayer vimos un problema clásico de programación dinámica, pero que tiene relación con otras técnicas:http://www.blogger.com/img/blank.gif

Máxima subsecuencia creciente
Explicación en Algorithmist
Explicación en Wikipedia

El problema consiste en, dada una secuencia de números, encontrar la subsecuencia más larga de números ordenados en forma creciente (no necesariamente consecutivos).

Ejemplo:
En la secuencia 3 1 4 5 2 17 8 11
La secuencia más larga es 3 4 5 8 11, con longitud 5.

Ayer vimos una solución sencilla que tarda o(n^2)
También vimos una solución que usa busqueda binaria, o trucos equivalentes, para reducir la complejidad a o(n*logn).

Si alguno se anima, puede dejar en los comentarios un programa que resuleva el problema!

Nico