Subsecuencia creciente más larga (LIS)

Nos dan un arreglo con $n$ números: $a[0 \dots n-1]$. La tarea es encontrar la subsecuencia estrictamente creciente más larga en $a$.

Formalmente buscamos la secuencia más larga de índices $i_1, \dots i_k$ tal que

$$i_1 < i_2 < \dots < i_k,\quad a[i_1] < a[i_2] < \dots < a[i_k]$$

En este artículo discutimos varios algoritmos para resolver esta tarea. También discutiremos algunos otros problemas que se pueden reducir a este problema.

Solución en $O(n^2)$ con programación dinámica {data-toc-label=“Solución en O(n^2) con programación dinámica”}

La programación dinámica es una técnica muy general que permite resolver una clase enorme de problemas. Aquí aplicamos la técnica a nuestra tarea específica.

Primero buscaremos solo la longitud de la subsecuencia creciente más larga, y recién después aprenderemos a reconstruir la subsecuencia en sí.

Encontrar la longitud

Para completar esta tarea, definimos un arreglo $d[0 \dots n-1]$, donde $d[i]$ es la longitud de la subsecuencia creciente más larga que termina en el elemento del índice $i$.

Calcularemos este arreglo de a poco: primero $d[0]$, después $d[1]$, y así sucesivamente. Después de calcular este arreglo, la respuesta al problema será el valor máximo en el arreglo $d[]$.

Sea el índice actual $i$. Es decir, queremos calcular el valor $d[i]$ y todos los valores anteriores $d[0], \dots, d[i-1]$ ya se conocen. Entonces hay dos opciones:

• $d[i] = 1$: la subsecuencia buscada consiste solo del elemento $a[i]$.

• $d[i] > 1$: la subsecuencia terminará en $a[i]$, y justo antes habrá algún número $a[j]$ con $j < i$ y $a[j] < a[i]$.

  Es fácil ver que la subsecuencia que termina en $a[j]$ será a su vez una de las subsecuencias crecientes más largas que terminan en $a[j]$. El número $a[i]$ solo extiende esa subsecuencia creciente más larga en un número.

  Por lo tanto, podemos iterar sobre todos los $j < i$ con $a[j] < a[i]$, y tomar la secuencia más larga que obtenemos al agregar $a[i]$ a la subsecuencia creciente más larga que termina en $a[j]$. La subsecuencia creciente más larga que termina en $a[j]$ tiene longitud $d[j]$, y extenderla en uno da la longitud $d[j] + 1$.

  $$d[i] = \max_{\substack{j < i \\ a[j] < a[i]}} \left(d[j] + 1\right)$$

Si combinamos estos dos casos obtenemos la respuesta final para $d[i]$:

$$d[i] = \max\left(1, \max_{\substack{j < i \\ a[j] < a[i]}} \left(d[j] + 1\right)\right)$$

Implementación

Aquí hay una implementación del algoritmo descrito arriba, que calcula la longitud de la subsecuencia creciente más larga.

int lis(vector<int> const& a) {
    int n = a.size();
    vector<int> d(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i])
                d[i] = max(d[i], d[j] + 1);
        }
    }

    int ans = d[0];
    for (int i = 1; i < n; i++) {
        ans = max(ans, d[i]);
    }
    return ans;
}

Reconstruir la subsecuencia

Hasta ahora solo aprendimos a encontrar la longitud de la subsecuencia, pero no a encontrar la subsecuencia en sí.

Para poder reconstruir la subsecuencia generamos un arreglo auxiliar adicional $p[0 \dots n-1]$ que calcularemos junto con el arreglo $d[]$. $p[i]$ será el índice $j$ del penúltimo elemento en la subsecuencia creciente más larga que termina en $i$. En otras palabras, el índice $p[i]$ es el mismo índice $j$ en el que se obtuvo el valor más alto $d[i]$. Este arreglo auxiliar $p[]$ apunta, en cierto sentido, a los ancestros.

Después, para obtener la subsecuencia, solo empezamos en el índice $i$ con el $d[i]$ máximo, y seguimos a los ancestros hasta deducir la subsecuencia completa, es decir, hasta llegar al elemento con $d[i] = 1$.

Implementación de la reconstrucción

Cambiaremos un poco el código de las secciones anteriores. Calcularemos el arreglo $p[]$ junto con $d[]$, y después calcularemos la subsecuencia.

Por conveniencia, inicialmente asignamos los ancestros con $p[i] = -1$. Para elementos con $d[i] = 1$, el valor de los ancestros permanecerá $-1$, lo cual será un poco más conveniente para reconstruir la subsecuencia.

vector<int> lis(vector<int> const& a) {
    int n = a.size();
    vector<int> d(n, 1), p(n, -1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && d[i] < d[j] + 1) {
                d[i] = d[j] + 1;
                p[i] = j;
            }
        }
    }

    int ans = d[0], pos = 0;
    for (int i = 1; i < n; i++) {
        if (d[i] > ans) {
            ans = d[i];
            pos = i;
        }
    }

    vector<int> subseq;
    while (pos != -1) {
        subseq.push_back(a[pos]);
        pos = p[pos];
    }
    reverse(subseq.begin(), subseq.end());
    return subseq;
}

Forma alternativa de reconstruir la subsecuencia

También es posible reconstruir la subsecuencia sin el arreglo auxiliar $p[]$. Simplemente podemos recalcular el valor actual de $d[i]$ y ver también cómo se alcanzó el máximo.

Este método lleva a un código un poco más largo, pero a cambio ahorramos algo de memoria.

Solución en $O(n \log n)$ con programación dinámica y búsqueda binaria {data-toc-label=“Solución en O(n log n) con programación dinámica y búsqueda binaria”}

Para obtener una solución más rápida del problema, construimos una solución distinta de programación dinámica que corre en $O(n^2)$, y después la mejoramos a $O(n \log n)$.

Usaremos el arreglo de programación dinámica $d[0 \dots n]$. Esta vez $d[l]$ no corresponde al elemento $a[i]$ ni a un prefijo del arreglo. $d[l]$ será el elemento más pequeño en el que termina una subsecuencia creciente de longitud $l$.

Inicialmente asumimos $d[0] = -\infty$ y para todas las demás longitudes $d[l] = \infty$.

Procesaremos de nuevo los números de a poco, primero $a[0]$, después $a[1]$, etc., y en cada paso mantendremos el arreglo $d[]$ actualizado.

Al procesar $a[i]$, podemos preguntarnos: ¿qué condiciones tienen que cumplirse para que escribamos el número actual $a[i]$ en el arreglo $d[0 \dots n]$?

Ponemos $d[l] = a[i]$ si existe una subsecuencia creciente más larga de longitud $l$ que termina en $a[i]$, y no existe una subsecuencia creciente más larga de longitud $l$ que termine en un número más pequeño. De forma similar al enfoque anterior, si quitamos el número $a[i]$ de la subsecuencia creciente más larga de longitud $l$, obtenemos otra subsecuencia creciente más larga de longitud $l -1$. Así que queremos extender una subsecuencia creciente más larga de longitud $l - 1$ con el número $a[i]$, y obviamente la subsecuencia creciente más larga de longitud $l - 1$ que termina con el elemento más pequeño funcionará mejor; en otras palabras, la secuencia de longitud $l-1$ que termina en el elemento $d[l-1]$.

Existe una subsecuencia creciente más larga de longitud $l - 1$ que podemos extender con el número $a[i]$ exactamente si $d[l-1] < a[i]$. Así que podemos iterar sobre cada longitud $l$ y comprobar si podemos extender una subsecuencia creciente más larga de longitud $l - 1$ verificando el criterio.

Además también hay que comprobar si tal vez ya encontramos una subsecuencia creciente más larga de longitud $l$ con un número más pequeño al final. Así que solo actualizamos si $a[i] < d[l]$.

Después de procesar todos los elementos de $a[]$ la longitud de la subsecuencia deseada es el mayor $l$ con $d[l] < \infty$.

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> d(n+1, INF);
    d[0] = -INF;

    for (int i = 0; i < n; i++) {
        for (int l = 1; l <= n; l++) {
            if (d[l-1] < a[i] && a[i] < d[l])
                d[l] = a[i];
        }
    }

    int ans = 0;
    for (int l = 0; l <= n; l++) {
        if (d[l] < INF)
            ans = l;
    }
    return ans;
}

Ahora hacemos dos observaciones importantes.

1. El arreglo $d$ siempre estará ordenado: $d[l-1] < d[l]$ para todo $i = 1 \dots n$.

   Esto es trivial, porque se puede quitar el último elemento de la subsecuencia creciente de longitud $l$ y se obtiene una subsecuencia creciente de longitud $l-1$ con un número final más pequeño.

2. El elemento $a[i]$ actualizará a lo sumo un valor $d[l]$.

   Esto se sigue de inmediato de la implementación de arriba. Solo puede haber un lugar en el arreglo con $d[l-1] < a[i] < d[l]$.

Así podemos encontrar este elemento en el arreglo $d[]$ usando búsqueda binaria en $O(\log n)$. De hecho, simplemente podemos buscar en el arreglo $d[]$ el primer número estrictamente mayor que $a[i]$, e intentar actualizar este elemento de la misma forma que en la implementación de arriba.

Implementación

Esto nos da la implementación mejorada en $O(n \log n)$:

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> d(n+1, INF);
    d[0] = -INF;

    for (int i = 0; i < n; i++) {
        int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
        if (d[l-1] < a[i] && a[i] < d[l])
            d[l] = a[i];
    }

    int ans = 0;
    for (int l = 0; l <= n; l++) {
        if (d[l] < INF)
            ans = l;
    }
    return ans;
}

Reconstruir la subsecuencia

También es posible reconstruir la subsecuencia con este enfoque. Esta vez hay que mantener dos arreglos auxiliares. Uno que nos dice el índice de los elementos en $d[]$. Y de nuevo hay que crear un arreglo de “ancestros” $p[i]$. $p[i]$ será el índice del elemento anterior para la subsecuencia óptima que termina en el elemento $i$.

Es fácil mantener estos dos arreglos durante la iteración sobre el arreglo $a[]$ junto con los cálculos de $d[]$. Y al final no es difícil reconstruir la subsecuencia deseada usando estos arreglos.

Solución en $O(n \log n)$ con estructuras de datos {data-toc-label=“Solución en O(n log n) con estructuras de datos”}

En lugar del método de arriba para calcular la subsecuencia creciente más larga en $O(n \log n)$ también podemos resolver el problema de otra forma: usando algunas estructuras de datos simples.

Volvamos al primer método. Recordemos que $d[i]$ es el valor $d[j] + 1$ con $j < i$ y $a[j] < a[i]$.

Así, si definimos un arreglo adicional $t[]$ tal que

$$t[a[i]] = d[i],$$

entonces el problema de calcular el valor $d[i]$ es equivalente a encontrar el valor máximo en un prefijo del arreglo $t[]$:

$$d[i] = \max\left(t[0 \dots a[i] - 1] + 1\right)$$

El problema de encontrar el máximo de un prefijo de un arreglo (que cambia) es un problema estándar que se puede resolver con muchas estructuras de datos distintas. Por ejemplo, podemos usar un Árbol de Segmentos o un Árbol de Fenwick.

Este método tiene obviamente algunas desventajas: en cuanto a longitud y complejidad de la implementación, este enfoque será peor que el método que usa búsqueda binaria. Además, si los números de entrada $a[i]$ son especialmente grandes, tendríamos que usar algunos trucos, como comprimir los números (es decir, renumerarlos de $0$ a $n-1$), o usar un árbol de segmentos dinámico (generar solo las ramas del árbol que son importantes). Si no, el consumo de memoria será demasiado alto.

Por otro lado, este método también tiene algunas ventajas: con este método no hay que pensar en propiedades rebuscadas de la solución de programación dinámica. Y este enfoque nos permite generalizar el problema con mucha facilidad (ver más abajo).

Tareas relacionadas

Aquí hay varios problemas que están estrechamente relacionados con el problema de encontrar la subsecuencia creciente más larga.

Subsecuencia no decreciente más larga

De hecho esto es casi el mismo problema. Solo que ahora está permitido usar números idénticos en la subsecuencia.

La solución es esencialmente también casi la misma. Solo hay que cambiar los signos de desigualdad, y hacer una ligera modificación a la búsqueda binaria.

Número de subsecuencias crecientes más largas

Podemos usar el primer método discutido, ya sea la versión $O(n^2)$ o la versión con estructuras de datos. Solo hay que guardar además de cuántas formas podemos obtener subsecuencias crecientes más largas que terminan en los valores $d[i]$.

El número de formas de formar una subsecuencia creciente más larga que termina en $a[i]$ es la suma de todas las formas para todas las subsecuencias crecientes más largas que terminan en $j$ donde $d[j]$ es máximo. Puede haber varios de esos $j$, así que hay que sumarlos todos.

Usando un Árbol de Segmentos este enfoque también se puede implementar en $O(n \log n)$.

No es posible usar el enfoque de búsqueda binaria para esta tarea.

Menor número de subsecuencias no crecientes que cubren una secuencia

Para un arreglo dado con $n$ números $a[0 \dots n - 1]$ hay que colorear los números con la menor cantidad de colores, de modo que cada color forme una subsecuencia no creciente.

Para resolver esto, notamos que el número mínimo de colores requeridos es igual a la longitud de la subsecuencia creciente más larga.

Demostración: Hay que demostrar la dualidad de estos dos problemas.

Denotemos por $x$ la longitud de la subsecuencia creciente más larga y por $y$ el menor número de subsecuencias no crecientes que forman una cubierta. Hay que demostrar que $x = y$.

Es claro que $y < x$ no es posible, porque si tenemos $x$ elementos estrictamente crecientes, entonces ningún par puede ser parte de la misma subsecuencia no creciente. Por lo tanto tenemos $y \ge x$.

Ahora mostramos que $y > x$ no es posible, por contradicción. Supongamos que $y > x$. Entonces consideramos cualquier conjunto óptimo de $y$ subsecuencias no crecientes. Transformamos este conjunto de la siguiente forma: mientras haya dos de esas subsecuencias tales que la primera empiece antes que la segunda, y la primera secuencia empiece con un número mayor o igual que el de la segunda, entonces desenganchamos este número inicial y lo adherimos al comienzo de la segunda. Después de un número finito de pasos tenemos $y$ subsecuencias, y sus números iniciales formarán una subsecuencia creciente de longitud $y$. Como asumimos que $y > x$ llegamos a una contradicción.

Así se sigue que $y = x$.

Reconstrucción de las secuencias: La partición deseada de la secuencia en subsecuencias se puede hacer de forma voraz. Es decir, recorremos de izquierda a derecha y asignamos el número actual a aquella subsecuencia que termina con el número mínimo que es mayor o igual que el actual.

Problemas de práctica

• ACMSGURU - “North-East” 
• Codeforces - LCIS 
• Codeforces - Tourist 
• SPOJ - DOSA 
• SPOJ - HMLIS 
• SPOJ - ONEXLIS 
• SPOJ - SUPPER 
• Topcoder - AutoMarket 
• Topcoder - BridgeArrangement 
• Topcoder - IntegerSequence 
• UVA - Back To Edit Distance 
• UVA - Happy Birthday 
• UVA - Tiling Up Blocks