Longest Increasing Subsequence (LIS) encuentra la subsecuencia más larga donde cada elemento es estrictamente mayor que el anterior. Es un problema DP clásico con una solución óptima O(n log n) usando patience sorting.

La versión DP naïve es O(n²), pero existe un método más rápido que combina DP con búsqueda binaria sobre pilas de valores.

Cómo Funciona

DP O(n²)

dp[i] = longitud LIS terminando en índice i.

dp[i] = 1 + max(dp[j] for j < i if A[j] < A[i])

Patience Sorting O(n log n)

Mantén un array tails donde tails[k] es el menor tail posible de una subsecuencia creciente de longitud k+1.

Para cada x en el array:

• Busca el primer tails[i] >= x
• Reemplaza tails[i] = x
• Si x es mayor que todos, añade a tails

Idea Clave

Patience sorting es la intuición: imagina barajar cartas y colocarlas en pilas donde cada pila tiene un top card mayor que las siguientes. El número de pilas al final es la longitud LIS. Mantener el menor tail posible en cada pila permite búsqueda binaria.

La propiedad clave: tails siempre está ordenado, por lo que lower_bound funciona en O(log n) por elemento.

Ejemplo Trabajado

A = [10, 9, 2, 5, 3, 7, 101, 18]

Proceso patience sorting:

• 10 → tails = [10]
• 9 → reemplaza 10 → tails = [9]
• 2 → reemplaza 9 → tails = [2]
• 5 → añade → tails = [2, 5]
• 3 → reemplaza 5 → tails = [2, 3]
• 7 → añade → tails = [2, 3, 7]
• 101 → añade → tails = [2, 3, 7, 101]
• 18 → reemplaza 101 → tails = [2, 3, 7, 18]

Resultado: longitud LIS = 4 ([2, 3, 7, 18] o [2, 3, 7, 101]).

Casos Extremos y Trampas

• Estrictamente creciente — A[i-1] < A[i], no <=. Usa lower_bound.
• No estrictamente creciente — usa upper_bound para permitir empates.
• Reconstrucción — mantén prev[i] y tails_idx para reconstruir la secuencia.
• Permutación — en toda permutación de [1..n], LIS × LDS ≥ n (Erdős–Szekeres).

Comparación

Aplicaciones

• Series temporales — detectar tendencias crecientes
• Bioinformática — alineamiento de secuencias
• Procesamiento de texto — diff, spell checkers
• Enseñanza — introduce patience sorting y binary search en DP

Trayectoria de Práctica

1. Implementa DP O(n²); traza el ejemplo con tablas dp y prev.
2. Implementa patience sorting O(n log n); usa bisect_left o binary search manual.
3. Añade reconstrucción: mantén tails_idx para mapear tails a índices originales.
4. ¿Por qué tails siempre está ordenado? Prueba con un contraejemplo.
5. Investiga Erdős–Szekeres: ¿cuántas secuencias crecientes/decrecientes garantiza una permutación?