1. Conceptos Básicos

Una subseccuencia de una secuencia A = [a₁, a₂, …, aₙ] es cualquier conjunto de elementos que conserva el orden original pero no necesariamente son contiguos. La subsecuencia es creciente si cada elemento es estrictamente mayor que el anterior.

Formalmente, buscamos la mayor longitud k tal que exista un índice i₁ < i₂ < … < iₖ con a_{i₁} < a_{i₂} < … < a_{iₖ}.

Ejemplo ilustrativo

Para la serie [10, 22, 9, 33, 21, 50, 41, 60, 80] una LIS válida es [10, 22, 33, 50, 60, 80] con longitud 6.

2. Implementación O(N²) – Programación Dinámica

def lis_dp(arr):
    """Devuelve la longitud de la LIS usando DP O(N²)."""
    n = len(arr)
    if n == 0:
        return 0
    # dp[i] = longitud de la LIS que termina en i
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
    return max(dp)
# Ejemplo de uso
seq = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print("LIS longitud:", lis_dp(seq))

Esta versión es fácil de entender y adecuada para n ≤ 10⁴. Su complejidad temporal es O(N²) y espacial O(N).

3. Implementación O(N log N) – Patience Sorting

La idea clave es mantener una lista tails donde tails[i] es el menor posible último elemento de una subsecuencia creciente de longitud i+1. Cada nuevo número se inserta con bisect_left, lo que garantiza O(log N) por iteración.

Complejidad

• Tiempo: O(N log N)
• Espacio: O(N) (solo tails y opcionalmente prev_idx para reconstruir).

import bisect
def lis_patience(arr):
    """Devuelve la longitud y la subsecuencia real usando O(N log N)."""
    if not arr:
        return 0, []
    # tails almacena los valores finales mínimos
    tails = []
    # parent[i] guarda el índice del elemento anterior en la LIS que termina en i
    parent = [-1] * len(arr)
    # pos[i] guarda la posición (longitud-1) donde arr[i] se inserta en tails
    pos = [0] * len(arr)
    for i, x in enumerate(arr):
        # búsqueda binaria en tails
        idx = bisect.bisect_left(tails, x)
        if idx == len(tails):
            tails.append(x)
        else:
            tails[idx] = x
        pos[i] = idx
        # actualizar puntero al anterior elemento de la subsecuencia
        if idx > 0:
            # buscar el último índice j < i con pos[j] == idx-1 y arr[j] < x
            # se puede mantener una lista de índices por longitud para O(1)
            # aquí usamos una búsqueda lineal simple (suficiente para demo)
            for j in range(i-1, -1, -1):
                if pos[j] == idx-1 and arr[j] < x:
                    parent[i] = j
                    break
    # reconstruir la LIS
    lis_len = len(tails)
    lis = []
    # encontrar el último índice con posición lis_len-1
    last = max(i for i, p in enumerate(pos) if p == lis_len-1)
    while last != -1:
        lis.append(arr[last])
        last = parent[last]
    lis.reverse()
    return lis_len, lis
# Demo
seq = [10, 22, 9, 33, 21, 50, 41, 60, 80]
length, subseq = lis_patience(seq)
print("Longitud:", length)
print("LIS:", subseq)

Esta versión escala a millones de elementos sin perder rendimiento.