Subsecuencia creciente más larga
DP O(n^2) y después el truco O(n log n)
Subsecuencia creciente más larga es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Qué es una LIS
Una subsecuencia conserva el orden, pero omite elementos. La subsecuencia creciente más larga es la secuencia de este tipo más larga que crece estrictamente.
a = [3, 1, 4, 1, 5, 9, 2]Subsecuencia, no subarreglo
A diferencia de un subarreglo, una LIS no tiene que ser contigua. Puede saltar números menores para mantener creciente la cadena.
El estado de DP O(n^2)
Sea dp[i] la longitud de la LIS que termina en el índice i. Cada elemento es, como mínimo, una subsecuencia de longitud uno por sí mismo.
dp = [1] * nLa transición O(n^2)
Para cada i, examine todos los j anteriores. Si a[j] es menor, extienda la subsecuencia: dp[i] = max(dp[i], dp[j] + 1).
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)Lea la respuesta
El resultado es el valor más grande de la tabla, ya que la LIS puede terminar en cualquier posición, no solo en el último índice.
answer = max(dp)Por qué O(n^2) puede superar el límite de tiempo
El doble bucle cuesta O(n cuadrado). Para valores de n cercanos a 100000, es demasiado lento y obtiene un veredicto de límite de tiempo.
La idea de patience sorting
El método más rápido mantiene una lista con la cola más pequeña posible para cada longitud de subsecuencia, como en patience sorting.
tails = []Use bisect para ubicar
Para cada número, busque mediante búsqueda binaria dónde encaja entre las colas usando bisect_left, con un coste total de O(n log n).
from bisect import bisect_leftExtienda o reemplace
Si la posición está después del final, use append para ampliar la LIS. De lo contrario, reemplace esa cola por el valor menor.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xLa longitud está en tails
Cuando termina el recorrido, len(tails) es la longitud de la LIS. La lista en sí no siempre es la subsecuencia; solo su longitud es exacta.
answer = len(tails)Estrictamente creciente frente a no decreciente
Para la variante no decreciente, cambie a bisect_right para que los valores iguales puedan ampliar la cadena.
from bisect import bisect_rightComprobación rápida
¿Qué método encuentra la longitud de la LIS en O(n log n)?
Resumen: de n^2 a n log n
Ahora puede resolver la LIS de dos formas. La DP de O(n^2) es sencilla; el método de colas más bisect escala para entradas grandes y evita superar el límite de tiempo.
Preguntas frecuentes
¿La lección «Subsecuencia creciente más larga» es gratis?
Sí — el texto completo de «Subsecuencia creciente más larga» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Subsecuencia creciente más larga»?
DP O(n^2) y después el truco O(n log n) Practicas Competitive Programming Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Subsecuencia creciente más larga»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Memoización frente a tabulación
- Defina el estado y la transición
- Escaleras y combinaciones de monedas
- Subsecuencia creciente más larga