Longest Increasing Subsequence
Recibes una lista de números enteros nums. Una subsecuencia conserva algunos de los elementos, en su orden original, y descarta el resto; los elementos conservados no tienen que estar uno al lado del otro. Devuelve la longitud de la subsecuencia más larga cuyos valores aumentan estrictamente de izquierda a derecha. Dos valores iguales seguidos no cuentan como un aumento.
Función
- numsinteger-array
- la lista de números enteros entre los que elegir
- Devuelveinteger
- la longitud de la subsecuencia estrictamente creciente más larga
Restricciones
1 ≤ nums.length ≤ 2500-104 ≤ nums[i] ≤ 104
Ejemplos
- Entrada
- nums = [3, 1, 8, 2, 5, 9, 4, 7]
- Salida
- 4
- Explicación
- Conservar 1, 2, 5, 9 da una subsecuencia creciente de longitud 4, y lo mismo ocurre con 1, 2, 5, 7 y 1, 2, 4, 7. Ninguna elección de cinco valores mantiene un orden creciente, así que la respuesta es 4.
- Entrada
- nums = [7, 7, 7, 7]
- Salida
- 1
- Explicación
- Los valores deben aumentar estrictamente, así que no puede haber dos 7 en la misma subsecuencia. Un solo elemento cuenta como subsecuencia, por lo que la respuesta es 1.
- Entrada
- nums = [12, -4, 0, 25, -10, 3, 16, 5]
- Salida
- 4
- Explicación
- -4, 0, 3, 16 tiene longitud 4 (-4, 0, 3, 5 también). Empezando por el primer elemento, 12, solo se obtienen dos valores, como 12, 25: la mejor subsecuencia no tiene por qué empezar al principio.
+20 pruebas ocultas al enviar
Para ir más allá
¿Puedes devolver una subsecuencia creciente más larga, no solo su longitud, y seguir ejecutándote en tiempo O(n log n)?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
La mejor subsecuencia de toda la lista es difícil de describir directamente. Haz una pregunta más concreta para cada índice
i: ¿cuál es la subsecuencia creciente más larga que termina exactamente connums[i]?Una subsecuencia que termina en
nums[i]está formada solo pornums[i]o continúa la mejor subsecuencia que termina en algúnnums[j] < nums[i]anterior. Elige el mejorjy suma uno. La respuesta es el mayor de estos valores, independientemente de dónde termine.Para conseguir una complejidad inferior a
O(n²), conserva para cada longitud solo el valor más pequeño con el que puede terminar una subsecuencia de esa longitud. Esos valores se mantienen ordenados, así que una búsqueda binaria te indica si un número nuevo amplía la subsecuencia más larga o reemplaza un valor final.
Solución
Una subsecuencia puede omitir cualquier elemento, así que una lista de n números tiene 2^n subsecuencias, demasiadas para comprobarlas. La solución con programación dinámica consiste en plantear una pregunta más concreta para cada índice: ¿cuánto mide la subsecuencia creciente más larga que termina exactamente aquí? Eso da una tabla de O(n²). La versión más rápida mantiene un número por cada longitud: el valor más pequeño con el que puede terminar una subsecuencia de esa longitud, y ubica cada elemento nuevo mediante una búsqueda binaria.
Tomar o saltar cada elemento
Correcto, pero no termina con las pruebas más grandes
Intuición
Recorre la lista y toma una decisión por elemento: conservarlo o excluirlo. Puedes conservar nums[i] solo cuando sea mayor que el último valor que conservaste. Una función recursiva longest(i, prev) responde a esta pregunta: si el último elemento conservado está en el índice prev (o en -1 si todavía no se ha conservado ninguno), ¿cuántos elementos más puedes añadir a partir del índice i?
Omitirlo da longest(i+1, prev). Conservarlo, cuando está permitido, da 1 + longest(i+1, i). La respuesta es el mayor de los dos valores y, cuando se llega al final de la lista, ya no se puede añadir nada más, así que el resultado es 0. Cada subsecuencia creciente es un camino de decisiones de conservar u omitir, así que la búsqueda no puede pasar por alto la mejor.
Es lento porque ambas ramas siguen abiertas siempre que los valores aumenten. En una lista como 1, 2, 3, ..., n, las llamadas se duplican con cada elemento: 2 elevado a la potencia de 40 ya supone aproximadamente 10^12 llamadas, y las pruebas grandes tienen 2500 elementos. Sin embargo, longest(i, prev) depende solo del par (i, prev), así que hay como máximo n² preguntas distintas. Hacer cada una una sola vez es el siguiente enfoque.
Algoritmo
- Escribe
longest(i, prev), dondepreves el índice del último elemento conservado, o-1. - Si
iha superado el final, devuelve 0. - Omite
nums[i]:best = longest(i+1, prev). - Si
preves-1onums[i] > nums[prev], consérvalo:best = max(best, 1 + longest(i+1, i)). - Devuelve
best. La respuesta eslongest(0, -1).
def lengthOfLIS(nums):
def longest(i, prev):
# The longest increasing subsequence of nums[i:] whose values all exceed nums[prev].
# prev is -1 while nothing has been taken.
if i == len(nums):
return 0
best = longest(i + 1, prev) # skip nums[i]
if prev == -1 or nums[i] > nums[prev]:
best = max(best, 1 + longest(i + 1, i)) # take nums[i]
return best
return longest(0, -1)Subsecuencia más larga que termina en cada índice
Intuición
Estado. Sea ending[i] la longitud de la subsecuencia creciente más larga cuyo último elemento es nums[i]. Fijar el último elemento es lo que permite dividir el problema claramente: una vez que sabes dónde termina una subsecuencia, sabes qué valores posteriores pueden seguirla.
Recurrencia. Si la subsecuencia que termina en nums[i] tiene más de un elemento, el elemento anterior a nums[i] es algún nums[j] con j < i y nums[j] < nums[i], y la parte hasta ese elemento debería ser lo más larga posible. Así que ending[i] = 1 + max(ending[j]) para esos valores de j. Caso base: cada elemento por sí solo es una subsecuencia, así que ending[i] empieza en 1. Orden: ending[i] solo lee índices menores, así que calcúlalo de izquierda a derecha.
Para [3, 1, 8, 2, 5, 9, 4, 7], la tabla es [1, 1, 2, 2, 3, 4, 3, 4]. Por ejemplo, 5 puede ir después de 3, 1 o 2, y el mejor de ellos es 2 con ending = 2, así que ending[4] = 3. La respuesta es la entrada más grande, 4, no la última: la mejor subsecuencia puede terminar en cualquier posición.
Cada índice revisa una vez cada índice anterior, así que el trabajo consiste en n(n-1)/2 comparaciones, unas 3.1 × 10^6 para n = 2500.
Algoritmo
- Crea
endingcon todas las entradas establecidas en 1. - Para cada
i, de izquierda a derecha, revisa cadaj < i. - Si
nums[j] < nums[i], estableceending[i]enending[j] + 1cuando ese valor sea mayor. - Devuelve el valor más grande de
ending.
def lengthOfLIS(nums):
n = len(nums)
# ending[i]: the longest increasing subsequence that ends with nums[i]
ending = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i] and ending[j] + 1 > ending[i]:
ending[i] = ending[j] + 1
return max(ending)Colas más pequeñas con búsqueda binaria
Intuición
La tabla anterior recuerda una longitud por índice. Puedes recordar menos: para cada longitud, solo el menor valor con el que puede terminar una subsecuencia creciente de esa longitud. Llámalo tails[k] para la longitud k+1. Un valor final menor siempre es al menos igual de bueno, porque cualquier valor que pueda ir después de una subsecuencia que termina en 9 también puede ir después de una que termina en 5.
tails siempre está ordenado en orden estrictamente creciente: una subsecuencia de longitud k+2 que termina en t contiene otra de longitud k+1 que termina por debajo de t. Así que, para cada nuevo valor x, busca mediante búsqueda binaria la primera cola que sea ≥ x. Si no hay ninguna, x es mayor que todas las colas y amplía la subsecuencia más larga, así que añádelo. De lo contrario, reemplaza esa cola por x: la subsecuencia de una longitud menos termina por debajo de x, así que añadir x da la misma longitud con un valor final menor.
Para [3, 1, 8, 2, 5, 9, 4, 7], tails pasa por [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7], y su longitud 4 es la respuesta. En el paso [1, 2, 4, 9], el 4 apareció después del 9 en la entrada, así que tails no es en sí una subsecuencia; solo su longitud tiene significado. El método también se llama ordenamiento por paciencia, por el juego de cartas en el que cada cola es la carta superior de una pila.
Procesar cada elemento cuesta una búsqueda binaria entre como máximo n colas: unos 2500 × 12 = 30 000 pasos para la entrada más grande.
Algoritmo
- Empieza con una lista vacía
tails. - Para cada
xennums, busca mediante búsqueda binaria el primer índicektal quetails[k] ≥ x. - Si ningún elemento de
tailses≥ x, añadex. - En caso contrario, establece
tails[k] = x. - Devuelve la longitud de
tails.
from bisect import bisect_left
def lengthOfLIS(nums):
# tails[k]: the smallest last value of any increasing subsequence of length k + 1
tails = []
for x in nums:
k = bisect_left(tails, x) # the first tail that is >= x
if k == len(tails):
tails.append(x) # x extends the longest subsequence so far
else:
tails[k] = x # x is a smaller ending for length k + 1
return len(tails)
Errores comunes y casos límite
La mayoría de las respuestas incorrectas se deben a confundir qué contiene la tabla o a tratar los valores iguales como si fueran crecientes.
- Devolver
ending[n-1]en lugar de la entrada más grande. Para[1, 2, 3, 0], la última entrada es 1, pero la respuesta es 3. - Comparar con
≤en lugar de<.[7, 7, 7, 7]debe devolver 1, no 4. - En la versión de colas, buscar la primera cola
> xen lugar de≥ x. Con duplicados, eso agrega el segundo 7 después del primero y cuenta los valores iguales como una subsecuencia más larga. - Tratar
tailscomo si fuera la subsecuencia misma. Sus valores pueden provenir de distintas subsecuencias, así que imprímela solo si llevas un seguimiento separado de los elementos anteriores. - Resolver por error la versión contigua. En
[3, 1, 8, 2, 5, 9, 4, 7], la secuencia creciente más larga de elementos vecinos es 2, 5, 9 (longitud 3), mientras que la respuesta es 4. - En Lua y R, los arreglos empiezan en 1, así que el marcador basado en 0
prev = -1pasa a ser 0 y la búsqueda binaria se ejecuta sobre los índices del 1 al tamaño actual.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de la subsecuencia creciente más larga?
El método tails se ejecuta en tiempo O(n log n) y ocupa O(n) de espacio: una búsqueda binaria por elemento. La tabla de programación dinámica que considera cada par de índices requiere O(n²) de tiempo, y probar cada subsecuencia requiere O(2ⁿ). Para n = 2500, eso equivale aproximadamente a 30 000, 3 millones y un número astronómico de pasos.
¿Por qué el método de ordenación por paciencia da la longitud correcta?
Después de cada elemento, tails[k] contiene el valor más pequeño con el que puede terminar cualquier subsecuencia creciente de longitud k+1 vista hasta el momento. Solo se añade cuando x es mayor que todas las colas, lo que significa que ahora existe una subsecuencia una unidad más larga que cualquiera anterior. Reemplazar nunca cambia la longitud; solo reduce un valor final, por lo que la longitud de la lista siempre es la longitud de la subsecuencia creciente más larga.
¿Cómo obtienes la subsecuencia creciente más larga real, no solo su longitud?
Registra un padre para cada elemento. En la tabla O(n²), el padre de i es el j que dio a ending[i] su valor. En el método de colas, almacena el índice del elemento detrás de cada cola y, al colocar un elemento, establece su padre como el índice almacenado una posición a su izquierda. Después, recorre los padres desde el final de la subsecuencia más larga y revierte el resultado.
¿Cómo encuentras la subsecuencia no decreciente más larga?
Permite vecinos iguales. En la tabla, usa nums[j] ≤ nums[i]. En el método de las colas, busca la primera cola que sea estrictamente mayor que x en lugar de mayor o igual, de modo que un valor igual extienda la lista en lugar de reemplazar una cola. [7, 7, 7, 7] después devuelve 4.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def lengthOfLIS(nums):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
nums = [3, 1, 8, 2, 5, 9, 4, 7]
Esperado
4