Tema
Subsecuencia creciente más larga
- Algoritmos
- Nivel intermedio
Dada una sucesión de números, se busca la subsecuencia más larga cuyos elementos aparecen en el mismo orden y crecen de forma estricta.
Nombre en inglés
Longest increasing subsequence
Intuición
La definición que cierra la recurrencia es T[i] igual a la longitud de la mejor subsecuencia que termina justo en la posición i. Al fijar el final, cada candidato solo mira hacia atrás y se queda con el mejor predecesor menor que él. La respuesta no es la última casilla, sino el máximo de toda la tabla, detalle que se olvida a menudo.
Fórmula
T[i] = 1 + max{ T[j] : j < i y a_j < a_i } ; respuesta = max_i T[i] ; coste O(n^2)
Ejemplo resuelto
Para la sucesión 3, 1, 4, 2, 5 la tabla queda en 1, 1, 2, 2, 3. La casilla del 4 vale 2 porque se apoya en el 3 o en el 1; la del 2 vale 2 porque se apoya en el 1; y la del 5 vale 3 porque se apoya en el 4 o en el 2. El máximo de la tabla es 3, que corresponde a 1, 4, 5 o bien a 1, 2, 5.
Errores frecuentes
- Devolver la última casilla en lugar del máximo de la tabla: La mejor subsecuencia no tiene por qué terminar en el último elemento.
- Confundir subsecuencia con subcadena: La subsecuencia admite huecos y la subcadena exige posiciones contiguas.
- Olvidar si el crecimiento es estricto: Con elementos repetidos, permitir la igualdad cambia la respuesta, y el enunciado del examen siempre lo precisa.
Ejercicio
¿Cuál es la longitud de la subsecuencia creciente más larga de 10, 9, 2, 5, 3, 7, 101, 18?
Ver la solución
Una de las mejores es 2, 3, 7, 18, y también sirve 2, 5, 7, 101. Ninguna alcanza cinco elementos.
Respuesta: 4