Longest Increasing Subsequence

Q: ¿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 para cada par de índices requiere O(n²) de tiempo, y probar cada subsecuencia requiere O(2ⁿ) .

Q: ¿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 estrictamente mayor que x , de modo que un valor igual extienda la lista en lugar de reemplazar una cola. [7, 7, 7, 7] después devuelve 4.

MedioProgramación dinámica Búsqueda binaria

+10

Recibes una lista de 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

lengthOfLIS(nums: integer-array) → integer

numsinteger-array: la lista de enteros entre los que elegir
Devuelveinteger: la longitud de la subsecuencia estrictamente creciente más larga

Restricciones

1 ≤ nums.length ≤ 2500
-10⁴ ≤ nums[i] ≤ 10⁴

Ejemplos

Entrada: nums = [3, 1, 8, 2, 5, 9, 4, 7]
Salida: 4
Explicación: 1, 2, 5, 9 aumenta, y lo mismo ocurre con 1, 2, 5, 7 y 1, 2, 4, 7: longitud 4. Ninguna elección de cinco valores sigue aumentando.

Para ir más allá

¿Puedes devolver una subsecuencia creciente más larga, junto con 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.

0 de 3 abiertas

Solución

Una lista de n números tiene 2^n subsecuencias, demasiadas para revisarlas. Preguntar, para cada índice, cuánto mide la mejor subsecuencia creciente que termina exactamente ahí da como resultado una tabla de O(n²). La versión más rápida mantiene, para cada longitud, el menor valor con el que puede terminar una subsecuencia de esa longitud y coloca cada elemento mediante una búsqueda binaria.

Toma o salta cada elemento

Correcto, pero no termina con las pruebas más grandes

Intuición

Decide para cada elemento si conservarlo; solo puedes conservar nums[i] cuando sea mayor que el último valor conservado. longest(i, prev) es el máximo de elementos que aún puedes añadir a partir del índice i, cuando el último elemento conservado está en prev (o -1). Si lo omites, obtienes longest(i+1, prev); si lo conservas, obtienes 1 + longest(i+1, i). Cada subsecuencia creciente es un camino de estas decisiones.

Con 1, 2, 3, ..., n, ambas ramas siguen abiertas y las llamadas se duplican con cada elemento: 2^40 ya es aproximadamente 10^12. Sin embargo, hay como máximo n² pares distintos (i, prev).

Algoritmo

Escribe longest(i, prev), donde prev es el índice del último elemento conservado, o -1.
Si i ha superado el final, devuelve 0.
Omite nums[i]: best = longest(i+1, prev).
Si prev es -1 o nums[i] > nums[prev], consérvalo: best = max(best, 1 + longest(i+1, i)).
Devuelve best. La respuesta es longest(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

Sea ending[i] la longitud de la subsecuencia creciente más larga cuyo último elemento es nums[i]. El elemento anterior a nums[i], si existe, es algún nums[j] con j < i y nums[j] < nums[i], y la parte hasta él debería ser lo más larga posible. Así que ending[i] = 1 + max(ending[j]) para esos valores de j, o 1 si no hay ninguno. Complétala de izquierda a derecha.

Para [3, 1, 8, 2, 5, 9, 4, 7], la tabla es [1, 1, 2, 2, 3, 4, 3, 4]: 5 puede ir después de 3, 1 o 2, y el mejor de ellos tiene longitud 2, así que ending[4] = 3. La respuesta es la entrada más grande, ya que la mejor subsecuencia puede terminar en cualquier posición.

n(n-1)/2 comparaciones: aproximadamente 3.1 × 10^6 para n = 2500.

Algoritmo

Crea ending con todas las entradas establecidas en 1.
Para cada i, de izquierda a derecha, revisa cada j < i.
Si nums[j] < nums[i], establece ending[i] en ending[j] + 1 si ese valor es 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

Para cada longitud, conserva solo el valor más pequeño con el que puede terminar una subsecuencia creciente de esa longitud: tails[k] para la longitud k+1. Un valor final más pequeño nunca es peor: cualquier valor que pueda ir después de un 9 puede ir después de un 5. tails se mantiene estrictamente creciente: elimina el último valor de una subsecuencia creciente de longitud k+2 y obtienes una de longitud k+1 que termina en un valor menor.

Para cada x, busca mediante búsqueda binaria la primera cola ≥ x. Si no hay ninguna, añade x: así se extiende la más larga. De lo contrario, reemplaza esa cola por x: la subsecuencia de una longitud menos termina por debajo de x, así que x da la misma longitud con un valor final menor.

Por ejemplo, para 1, tails pasa por [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7]: longitud 4. En [1, 2, 4, 9], el 4 apareció después del 9, así que solo la longitud de tails tiene significado.

Algoritmo

Empieza con una lista vacía tails.
Para cada x en nums, busca mediante búsqueda binaria el primer índice k tal que tails[k] ≥ x.
Si ningún elemento de tails es ≥ x, añade x.
De lo 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

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 tails, buscar la primera cola > x en lugar de ≥ x. Así, el segundo 7 se añade después del primero, contando los valores iguales como crecientes.
Resolver por error la versión contigua. En el ejemplo 1, la secuencia creciente más larga de elementos vecinos es 2, 5, 9 (longitud 3), mientras que la respuesta es 4.
Mantener índices desde 0 en Lua o R, donde los arreglos empiezan en 1. El marcador prev = -1 pasa a ser 0, y la búsqueda binaria se ejecuta en los índices del 1 al tamaño actual.

Preguntas frecuentes3

¿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 para cada par de índices requiere O(n²) de tiempo, y probar cada subsecuencia requiere O(2ⁿ).

¿Qué es la ordenación por paciencia en la subsecuencia creciente más larga?

Es el método de las colas, llamado así por un juego de cartas. Cada cola es la carta superior de una pila: una carta se coloca en la pila más a la izquierda cuya carta superior tiene un valor al menos igual al suyo, o inicia una nueva pila. El número de pilas es la respuesta.

¿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 estrictamente mayor que x, de modo que un valor igual extienda la lista en lugar de reemplazar una cola. [7, 7, 7, 7] después devuelve 4.

def lengthOfLIS(nums):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

nums = [3, 1, 8, 2, 5, 9, 4, 7]

Salida Esperada

Longest Increasing Subsequence

Función

Restricciones

Ejemplos

Pistas

Solución

Toma o salta cada elemento

Subsecuencia más larga que termina en cada índice

Colas más pequeñas con búsqueda binaria

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares