Subsecuencia creciente más larga (LIS)
Tema: Programación Dinámica · temarios: Syllabus OCI · Syllabus IOI
📍 Dónde se aprende: módulo 22 de la Ruta de Aprendizaje.
El problema: conservar el orden, permitiendo saltos
En a = [3,5,7,1,2,8] buscamos una subsecuencia estrictamente creciente
de longitud máxima. Una subsecuencia elige posiciones en su orden original,
pero puede saltarse elementos. «Estrictamente» exige que cada valor sea mayor
que el anterior; dos iguales no extienden la secuencia.
[3,5,7,8] es una respuesta de longitud 4. [1,2,7,8] no sirve:
el 7 aparece antes que el 1 y el 2 en el arreglo original.
Una primera DP: terminar en una posición
Definimos D[i] como la longitud máxima de una creciente que termina exactamente en a[i]. Puede contener solo a[i], dando longitud 1, o extender una subsecuencia terminada en una posición j<i con a[j]<a[i].
Por tanto, D[i] es el máximo entre 1 y todos los valores D[j]+1 admisibles.
Para nuestro ejemplo obtenemos [1,2,3,1,2,4]. La respuesta es el máximo
de D, no necesariamente su última casilla.
Este enfoque prueba O(n) predecesores por posición: O(n²) tiempo y O(n) memoria. Podemos evitar revisar tantos predecesores si guardamos una información más selectiva.
La idea rápida: el menor final para cada longitud
Entre dos crecientes de igual longitud, una que termina en 2 es más fácil de extender que una que termina en 5. Todo valor que sirve después de 5 sirve después de 2, y algunos adicionales también.
Guardamos cola[k] = el menor valor final posible de una creciente de longitud k+1
entre los elementos ya procesados. El nombre cola es el del vector del código;
no representa una cola FIFO ni guarda por sí mismo una subsecuencia.
Si el diagrama no cabe, deslízalo horizontalmente.
| Valor nuevo | Finales mínimos después de procesarlo | Interpretación |
|---|---|---|
| 3 | [3] | una creciente de longitud 1 termina en 3 |
| 5 | [3,5] | podemos alcanzar longitud 2 |
| 7 | [3,5,7] | podemos alcanzar longitud 3 |
| 1 | [1,5,7] | mejor final para longitud 1 |
| 2 | [1,2,7] | mejor final para longitud 2 |
| 8 | [1,2,7,8] | podemos alcanzar longitud 4 |
Después de ver el 1, no borramos la evidencia de que existía [3,5,7].
Cada casilla conserva una posibilidad para su propia longitud, no el
predecesor de la casilla siguiente. Por eso [1,2,7,8] no es una respuesta
válida aunque sea el vector final de resúmenes.
Por qué una búsqueda binaria encuentra la casilla correcta
Los finales mínimos están estrictamente ordenados: de una creciente de longitud k+1 podemos quitar su último elemento para obtener una de longitud k con final menor. Al llegar x, buscamos la primera casilla cuyo valor sea ≥x.
Si es la casilla k, los finales anteriores son menores que x: existe una creciente de longitud k que podemos extender, o empezamos una nueva si k=0. Reemplazar esa casilla por x mejora o conserva su final. No podemos extender una longitud mayor, porque su menor final ya es ≥x. Si no hay ninguna casilla ≥x, x extiende la mayor longitud conocida.
Implementación y llamada
int lis(const vector<int>& a) {
vector<int> cola; // cola[k] = el MENOR final posible de una creciente de largo k+1
for (int x : a) {
auto it = lower_bound(cola.begin(), cola.end(), x);
if (it == cola.end()) cola.push_back(x); // x extiende la más larga
else *it = x; // x mejora un final existente
}
return cola.size(); // ojo: NO es la subsecuencia en sí
}lis({3,5,7,1,2,8}) devuelve 4 y lis({}) devuelve 0. La implementación
necesita los encabezados de vector y lower_bound, y el espacio de nombres
estándar en el programa que la use.
lower_bound devuelve la primera posición con valor ≥x o end() si no existe.
Cada una de las n búsquedas cuesta O(log n), por lo que el total es
O(n log n) y la memoria adicional O(n). Para entender la operación de
búsqueda, consulta Búsqueda binaria clásica.
Repetidos y reconstrucción
Con [2,2,2], cada 2 reemplaza la primera casilla: la longitud estricta es 1.
Si el problema pide una subsecuencia no decreciente, que admite iguales,
se usa la primera posición >x, obtenida con upper_bound; entonces sería 3.
Para recuperar una subsecuencia real, guarda el índice que representa cada final y, para cada elemento, el índice de su predecesor en el momento de insertarlo. Al terminar, sigue los predecesores desde el representante de la mayor longitud y revierte ese recorrido. La función de esta ficha solo devuelve la longitud.
¿Ordenar el arreglo antes de aplicar el algoritmo simplifica el problema?
Cambia el problema: borra la restricción de respetar las posiciones originales. En el ejemplo produciría seis valores crecientes, cuando la respuesta original es cuatro. Procesamos el arreglo en su orden de entrada.
Más práctica en 22 - Programación dinámica II.