Subsecuencia creciente más larga (LIS)
Elige números de una lista, de izquierda a derecha, cada uno mayor que el anterior. ¿Qué longitud puede alcanzar una cadena así? La pregunta es lo bastante sencilla para un libro de acertijos, y su respuesta une un juego de cartas, una tabla clásica de programación dinámica y uno de los resultados más bellos sobre mezclas aleatorias.
El problema
Dada una lista de números, una subsecuencia conserva algunos de ellos en su orden original. Es creciente si cada valor es mayor que el anterior. La subsecuencia creciente más larga, o LIS, es la elección más larga de ese tipo. Una lista de n valores tiene 2ⁿ subsecuencias, así que comprobarlas todas solo funciona con listas muy cortas.
La tabla
Sea len[i] la longitud de la subsecuencia creciente más larga que termina exactamente en la posición i. Vale 1 para el valor solo, o 1 + len[j] para una posición anterior j cuyo valor es menor, lo que sea mayor. Cada posición mira hacia atrás a todas las anteriores, así que la tabla necesita n·(n − 1)/2 comparaciones. La respuesta es el mayor len[i], y anotar qué j dio cada len[i] permite leer la subsecuencia hacia atrás.
Un ejemplo
Toma 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. Posición por posición, las longitudes son 1, 2, 1, 1, 3, 2, 3, 4, 3 y 5: el 20 alarga 3, 10; el 4 alarga el 3; el 6 alarga el 4, el 7 el 6 y el 9 el 7. Leyendo hacia atrás desde el 9 se obtiene 3, 4, 6, 7, 9, una subsecuencia creciente de longitud 5.
Un método más rápido: el ordenamiento por paciencia
Reparte los valores como cartas en montones: cada valor va al montón más a la izquierda cuya carta de arriba no sea menor que él, o empieza un montón nuevo a la derecha. El número de montones es la longitud de la LIS. Como las cartas de arriba de los montones siempre están ordenadas, el montón correcto se encuentra con búsqueda binaria, así que todo el método tarda O(n log n) pasos. Debe su nombre al solitario (en inglés, patience) al que se parece.
Algo de matemáticas
En 1935, Paul Erdős y George Szekeres demostraron que toda lista de n² + 1 números distintos tiene una subsecuencia creciente o decreciente de longitud n + 1. En 1961, Stanislaw Ulam preguntó qué longitud tiene la LIS de una mezcla aleatoria de n números. La respuesta, cercana a 2√n para n grande, la resolvieron en 1977 Anatoly Vershik y Sergei Kerov y también Ben Logan y Larry Shepp, y en 1999 Jinho Baik, Percy Deift y Kurt Johansson encontraron la forma exacta de sus fluctuaciones: la distribución de Tracy–Widom de la teoría de matrices aleatorias.
Explóralo
Abre la aplicación y pulsa Paso. La columna naranja es la posición que se está calculando y la columna azul la posición anterior con la que se compara. La fila Longitud crece a medida que se encuentran cadenas más largas, la fila Va después de recuerda de dónde vienen, y al final la respuesta se lee hacia atrás en naranja y se muestra bajo la tabla.
Preguntas frecuentes
¿Cuál es la complejidad temporal de la LIS?
O(n²) con la tabla, porque cada posición mira todas las anteriores, y O(n log n) con el ordenamiento por paciencia y búsqueda binaria. Ambos necesitan O(n) de memoria.
¿Cómo encuentro la subsecuencia no decreciente más larga?
Deja que un valor vaya después de otro igual: compara con ≤ en lugar de <. En la aplicación, marca Permitir valores iguales. Con el ordenamiento por paciencia, pon cada valor en el montón más a la izquierda cuya carta de arriba sea estrictamente mayor.
¿Qué es la subsecuencia decreciente más larga?
El mismo problema con la comparación al revés, o la LIS de la lista con cada valor cambiado de signo. Según el teorema de Erdős–Szekeres, una lista lo bastante larga siempre tiene una subsecuencia creciente larga o una subsecuencia decreciente larga.
¿Qué longitud tiene la LIS de una lista aleatoria?
Para una mezcla aleatoria de n números distintos, cerca de 2√n para n grande. La corrección crece como la raíz sexta de n, así que para mil números la media es de unos 58, algo menos que 2√1000 ≈ 63.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba la subsecuencia creciente más larga