Celdas llenas
Comparaciones
Más larga hasta ahora

  • Llenándose
  • Leída
  • Respuesta

Más sobre la subsecuencia creciente más larga

Subsecuencia creciente más larga (LIS)

En una lista de números, ¿cuántos puedes elegir, manteniendo su orden, de modo que cada uno sea mayor que el anterior? La subsecuencia creciente más larga responde a esa pregunta. Escribe una lista y mira cómo la programación dinámica calcula, para cada posición, la cadena más larga que termina ahí. Pulsa Reproducir para ver cómo se llena la tabla, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. Escribe una lista de números. Para cada posición, la tabla guarda la longitud de la cadena creciente de valores más larga que termina ahí, y la posición anterior a la que continúa. Marca Permitir valores iguales para cadenas que nunca bajan. Al final, la cadena se lee hacia atrás desde su último valor. Nuevo ejemplo crea otra lista. Con el tablero seleccionado, las flechas avanzan o retroceden un paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.

Cómo funciona

  1. Escribe una lista de números, separados por comas o espacios. Marca Permitir valores iguales para cadenas que nunca bajan.
  2. Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto.
  3. Mira cómo cada posición se compara con todas las anteriores y luego ve la cadena más larga leída hacia atrás en naranja.

Cómo funciona la tabla

La tabla tiene tres filas: los valores, la longitud de la subsecuencia creciente más larga que termina en cada posición y la posición a la que continúa. Un valor solo es una cadena de longitud 1. Después se revisa cada posición anterior: si su valor es menor, la cadena que termina ahí se puede alargar con este valor, lo que da una longitud uno mayor. Gana el alargamiento más largo, y su posición va a la tercera fila.

Leer la cadena hacia atrás

La subsecuencia creciente más larga termina en la posición con la mayor longitud. Desde ahí, la tercera fila dice qué posición va antes, y la tercera fila de esa posición dice cuál va antes todavía, hasta llegar a una posición sin predecesor. Leídos en orden, esos valores son la respuesta. Con Permitir valores iguales marcado, un valor también puede ir después de otro igual, lo que da la cadena más larga que nunca baja.

Preguntas frecuentes

¿Qué diferencia hay entre una subsecuencia y un subarreglo?

Un subarreglo es un bloque de valores vecinos. Una subsecuencia mantiene el orden pero puede saltarse valores, así que en 3, 10, 2, 1, 20 los valores 3, 10 y 20 forman una subsecuencia creciente aunque 2 y 1 estén entre ellos.

¿Qué tan rápido es el algoritmo LIS?

El método de la tabla compara cada par de posiciones: n·(n − 1)/2 comparaciones para n valores. El ordenamiento por paciencia lo hace en O(n log n): guarda, para cada longitud, el menor valor que cierra una cadena de esa longitud, y coloca cada valor nuevo con búsqueda binaria.

¿La subsecuencia creciente más larga es única?

No siempre. En 1, 3, 2, 4, tanto 1, 3, 4 como 1, 2, 4 tienen longitud 3. La tabla da la longitud, y la lectura hacia atrás encuentra una de ellas.

¿Dónde se usa la subsecuencia creciente más larga?

Al comparar archivos y genomas, donde algunos métodos encuentran primero las líneas que coinciden y luego toman una subsecuencia creciente de sus posiciones; en planificación y en acertijos de apilar cajas; y en matemáticas, donde la longitud de la LIS de una mezcla aleatoria es un famoso objeto de estudio.

¿Se envía algo a algún sitio?

No. Todo se calcula en tu navegador, y tus últimos ajustes se quedan en el almacenamiento local de este navegador.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Ir al editor