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
Suscribirse a:
Enviar comentarios (Atom)
2 comentarios:
Dejo mi codigo para la solucion rapida http://codepad.org/oCxcpb8E
Brian
Publicar un comentario