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.

Tras 3,5,7315273Llega 1115273Llega 2112273Llega 811227384Índice de abajo:longitud

Si el diagrama no cabe, deslízalo horizontalmente.

Valor nuevoFinales mínimos después de procesarloInterpretació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.

Más práctica en 22 - Programación dinámica II.