Introducción al Problema de la Subsecuencia Creciente Más Larga (LIS)

El problema de la Subsecuencia Creciente Más Larga (LIS, por sus siglas en inglés, Longest Increasing Subsequence) es un desafío fundamental en la teoría de algoritmos y programación dinámica. Consiste en encontrar la longitud de la subsecuencia de números más larga dentro de una secuencia dada, con la condición de que todos los elementos de esta subsecuencia deben estar en orden estrictamente ascendente.

Exploraremos dos metodologías principales para resolver este problema: una basada en programación dinámica y otra más optimizada utilizando búsqueda binaria, que ofrece una complejidad temporal de O(n log n).

Enfoque 1: Programación Dinámica

La solución mediante programación dinámica es una forma intuitiva de abordar el problema LIS. La idea central es construir una tabla auxiliar, que aquí llamaremos maxLenEnFin, donde maxLenEnFin[i] almacenará la longitud de la subsecuencia creciente más larga que termina en el elemento numeros[i] de la secuencia original.

Definición de Estados y Transiciones:

• Para cada elemento numeros[i], su LIS más corta posible es de longitud 1 (el propio elemento). Así, inicializamos maxLenEnFin[i] = 1.
• Luego, para determinar la longitud real de la LIS que termina en numeros[i], examinamos todos los elementos numeros[j] que lo preceden (es decir, j < i).
• Si numeros[i] es mayor que numeros[j], significa que numeros[i] puede extender una subsecuencia creciente que termina en numeros[j]. En este caso, la longitud de la nueva LIS potencial sería maxLenEnFin[j] + 1.
• Actualizamos maxLenEnFin[i] con el valor máximo encontrado entre su longitud actual y maxLenEnFin[j] + 1.

Una vez que hemos procesado todos los elementos y llenado el arreglo maxLenEnFin, la longitud de la subsecuencia creciente más larga para toda la secuencia será simplemente el valor máximo presente en maxLenEnFin.

Implementación en Go (Programación Dinámica):

func encontrarLongitudLIS_DP(numeros []int) int {
    n := len(numeros)
    if n == 0 {
        return 0
    }

    // maxLenEnFin[i] guarda la longitud de la LIS que termina en numeros[i].
    maxLenEnFin := make([]int, n)

    for i := 0; i < n; i++ {
        maxLenEnFin[i] = 1 // Una LIS de longitud 1 con el elemento numeros[i] mismo.
        for j := 0; j < i; j++ {
            if numeros[i] > numeros[j] {
                // Si numeros[i] puede extender una LIS que termina en numeros[j],
                // actualizamos maxLenEnFin[i] si encontramos una LIS más larga.
                if maxLenEnFin[j]+1 > maxLenEnFin[i] {
                    maxLenEnFin[i] = maxLenEnFin[j] + 1
                }
            }
        }
    }

    // El resultado es la longitud máxima encontrada en el arreglo maxLenEnFin.
    maxTotalLen := 0
    for _, longitud := range maxLenEnFin {
        if longitud > maxTotalLen {
            maxTotalLen = longitud
        }
    }

    return maxTotalLen
}

Enfoque 2: Búsqueda Binaria (O(n log n))

El problema LIS puede resolverse de manera más eficiente con una complejidad temporal de O(n log n) utilizando una técnica que combina una iteración lineal con búsqueda binaria. Esta solución es más avanzada y se basa en el mantenimiento de un arreglo especial.

Concepto del Arreglo finalesLIS:

En lugar de almacenar las subsecuencias completas, mantenemos un arreglo, que llamaremos finalesLIS, que tiene una propiedad crucial: finalesLIS[k] almacena el valor más pequeño que puede ser el último elemento de una subsecuencia creciente de longitud k+1. Este arreglo finalesLIS se mantiene siempre ordenado en forma ascendente.

Cuando procesamos un nuevo número valorActual de la secuencia de entrada:

1. Realizamos una búsqueda binaria en finalesLIS para encontrar la posición (índice p) del primer elemento que sea mayor o igual a valorActual.
2. Si valorActual es mayor que todos los eleemntos en finalesLIS (es decir, la búsqueda binaria nos devuelve una posición más allá del final actual del arreglo), significa que podemos extender la subsecuencia creciente más larga existente. En este caso, simplemente añadimos valorActual al final de finalesLIS. La longitud de la LIS aumenta en 1.
3. Si encontramos un elemento en la posición p tal que finalesLIS[p] >= valorActual, lo reemplazamos con valorActual. Esto no cambia la longitud de la LIS (ya que la subsecuencia de lognitud p+1 sigue existiendo), pero mejora nuestra capacidad de formar subsecuencias más largas en el futuro, ya que ahora tenemos una LIS de longitud p+1 que termina con un número más pequeño.

La longitud del arreglo finalesLIS al final del proceso será la longitud de la subsecuencia creciente más larga.

Ejemplo Ilustrativo:

Consideremos la secuencia de entrada: [7, 8, 9, 1, 2, 3]

• Inicialmente, finalesLIS es []. La longitud LIS es 0.
• Procesar 7: 7 es mayor que todos en finalesLIS (vacío). Se añade. finalesLIS: [7]. Longitud LIS: 1.
• Procesar 8: 8 es mayor que todos en finalesLIS. Se añade. finalesLIS: [7, 8]. Longitud LIS: 2.
• Procesar 9: 9 es mayor que todos en finalesLIS. Se añade. finalesLIS: [7, 8, 9]. Longitud LIS: 3.
• Procesar 1: Búsqueda binaria para 1 en [7, 8, 9]. El primer elemento >= 1 es 7 (índice 0). Se reemplaza. finalesLIS: [1, 8, 9]. Longitud LIS: 3 (no cambia).
• Procesar 2: Búsqueda binaria para 2 en [1, 8, 9]. El primer elemento >= 2 es 8 (índice 1). Se reemplaza. finalesLIS: [1, 2, 9]. Longitud LIS: 3 (no cambia).
• Procesar 3: Búsqueda binaria para 3 en [1, 2, 9]. El primer elemento >= 3 es 9 (índice 2). Se reemplaza. finalesLIS: [1, 2, 3]. Longitud LIS: 3 (no cambia).

Al final, la longitud de finalesLIS es 3, que es la longitud correcta de la LIS para la secuencia dada.

Implementación en Go (Búsqueda Binaria):

func encontrarLongitudLIS_Binaria(elementos []int) int {
    if len(elementos) == 0 {
        return 0
    }

    // finalesLIS guarda los valores más pequeños que terminan una LIS de longitud `k+1` en `finalesLIS[k]`.
    // Este arreglo siempre está ordenado.
    finalesLIS := make([]int, 0, len(elementos)) // Inicializamos con capacidad, pero longitud 0.

    for _, valorActual := range elementos {
        // Realizamos una búsqueda binaria para encontrar la posición correcta para `valorActual`.
        // Buscamos el primer elemento en `finalesLIS` que sea mayor o igual a `valorActual`.
        inicio, fin := 0, len(finalesLIS)
        posicionInsercion := len(finalesLIS) // Por defecto, insertamos al final (extender LIS)

        for inicio < fin {
            medio := inicio + (fin-inicio)/2
            if finalesLIS[medio] < valorActual {
                inicio = medio + 1
            } else {
                fin = medio
            }
        }
        posicionInsercion = inicio

        // Si `posicionInsercion` es igual a la longitud actual de `finalesLIS`,
        // significa que `valorActual` es mayor que todos los elementos existentes,
        // por lo tanto, extendemos la LIS actual.
        if posicionInsercion == len(finalesLIS) {
            finalesLIS = append(finalesLIS, valorActual)
        } else {
            // De lo contrario, reemplazamos el elemento en `posicionInsercion`.
            // Esto nos da una LIS de la misma longitud pero con un "final" más pequeño,
            // lo que es beneficioso para futuras extensiones.
            finalesLIS[posicionInsercion] = valorActual
        }
    }

    // La longitud de `finalesLIS` es la longitud de la LIS más larga.
    return len(finalesLIS)
}