Se nos da una matriz con $n$ números: $a$.La tarea es encontrar la subsecuencia más larga, estrictamente creciente, en $a$.

Formalmente buscamos la sucesión más larga de índices $i_1, \dots i_k$ tal que$$i_1 < i_2 < \dots < i_k,\\da < a < \dots < a$$

En este artículo discutimos múltiples algoritmos para resolver esta tarea.También discutiremos algunos otros problemas, que pueden ser reducidos a este problema.

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 enorme clase de problemas.Aquí aplicamos la técnica para nuestra tarea específica.

Primero buscaremos sólo la longitud de la subsecuencia creciente más larga, y sólo después aprenderemos a restaurar la subsecuencia misma.

Encontrar la longitud

Para llevar a cabo esta tarea, definimos un array $d$, donde $d$ es la longitud de la subsecuencia creciente más larga que termina en el elemento del índice $i$.Vamos a calcular esta matriz gradualmente: primero $d$, luego $d$, y así sucesivamente.Después de calcular esta matriz, la respuesta al problema será el valor máximo de la matriz $d$.

Así que dejemos que el índice actual sea $i$.Es decir, queremos calcular el valor $d$ y ya se conocen todos los valores anteriores $d, \Ndots, d$.Entonces hay dos opciones:

• $d = 1$: la subsecuencia requerida consta sólo del elemento $a$.
• $d > 1$: entonces en la subsecuencia requerida hay otro número antes del número $a$.Centrémonos en ese número:puede ser cualquier elemento $a$ con $j = 0 \dots i-1$ y $a < a$.De esta manera podemos calcular $d$ utilizando la siguiente fórmula:Si fijamos el índice $j$, entonces la subsecuencia creciente más larga que termina en los dos elementos $a$ y $a$ tiene la longitud $d + 1$.Todos estos valores $d$ son ya conocidos, por lo que podemos calcular directamente $d$ con:$$d = \max_{{substack{j = 0 \dots i-1 \ a < a}} \Si combinamos estos dos casos obtenemos la respuesta final para $d$:

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

  Implementación

  Aquí se muestra una implementación del algoritmo descrito anteriormente, 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 < a) d = max(d, d + 1); } } int ans = d; for (int i = 1; i < n; i++) { ans = max(ans, d); } return ans;}

  Restauración de la subsecuencia

  Hasta ahora sólo hemos aprendido a encontrar la longitud de la subsecuencia, pero no a encontrar la subsecuencia en sí.

  Para poder recuperar la subsecuencia generamos una matriz auxiliar adicional $p$ que calcularemos junto a la matriz $d$.$p$ será el índice $j$ del penúltimo elemento de la subsecuencia creciente más larga terminada en $i$.En otras palabras el índice $p$ es el mismo índice $j$ en el que se obtuvo el mayor valor $d$.Esta matriz auxiliar $p$ apunta en cierto modo a los antecesores.

  Entonces para deducir la subsecuencia, simplemente empezamos en el índice $i$ con el máximo $d$, y seguimos los antecesores hasta deducir toda la subsecuencia, es decir, hasta llegar al elemento con $d = 1$.

  Implementación de restaurar

  Cambiaremos un poco el código de los apartados anteriores.Calcularemos el array $p$ junto a $d$, y posteriormente calcularemos la subsecuencia.

  Por comodidad asignamos originalmente los ancestros con $p = -1$.Para los elementos con $d = 1$, el valor de los ancestros seguirá siendo $-1$, lo que será un poco más conveniente para restaurar 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 < a && d < d + 1) { d = d + 1; p = j; } } } int ans = d, pos = 0; for (int i = 1; i < n; i++) { if (d > ans) { ans = d; pos = i; } } vector<int> subseq; while (pos != -1) { subseq.push_back(a); pos = p; } reverse(subseq.begin(), subseq.end()); return subseq;}

  Modo alternativo de restaurar la subsecuencia

  También es posible restaurar la subsecuencia sin el array auxiliar $p$.Podemos simplemente recalcular el valor actual de $d$ y también ver cómo se alcanzó el máximo.

  Este método conduce a un código ligeramente 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

  Con el fin de obtener una solución más rápida para el problema, construimos una solución de programación dinámica diferente que se ejecuta en $O(n^2)$, y luego la mejoramos a $O(n \log n)$.

  Utilizaremos la matriz de programación dinámica $d$.Esta vez $d$ será el elemento en el que termina una subsecuencia de longitud $i$.Si hay múltiples secuencias de este tipo, entonces tomamos la que termina en el elemento más pequeño.

  Inicialmente suponemos $d = -\infty$ y para todos los demás elementos $d = \infty$.

  Volvemos a procesar gradualmente los números, primero $a$, luego $a$, etc, y en cada paso mantenemos el array $d$ para que esté actualizado.

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

  int lis(vector<int> const& a) { int n = a.size(); const int INF = 1e9; vector<int> d(n+1, INF); d = -INF; for (int i = 0; i < n; i++) { for (int j = 1; j <= n; j++) { if (d < a && a < d) d = a; } } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

  Ahora hacemos dos observaciones importantes.

  El array $d$ estará siempre ordenado: $d \le d$ para todo $i = 1 \dots n$.Y también el elemento $a$ sólo actualizará como mucho un valor $d$.

  Por tanto, podemos encontrar este elemento en el array $d$ utilizando la búsqueda binaria en $O(\log n)$.De hecho simplemente estamos buscando en el array $d$ el primer número que sea estrictamente mayor que $a$, e intentamos actualizar este elemento de la misma manera que la implementación anterior.

  Implementación

  int lis(vector<int> const& a) { int n = a.size(); const int INF = 1e9; vector<int> d(n+1, INF); d = -INF; for (int i = 0; i < n; i++) { int j = upper_bound(d.begin(), d.end(), a) - d.begin(); if (d < a && a < d) d = a; } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

  Restauración de la subsecuencia

  También es posible restaurar la subsecuencia utilizando este enfoque.Esta vez tenemos que mantener dos matrices auxiliares.Una que nos dice el índice de los elementos en $d$.Y de nuevo tenemos que crear una matriz de «antecesores» $p$.$p$ será el índice del elemento anterior para la subsecuencia óptima que termina en el elemento $i$.

  Es fácil mantener estas dos matrices en el curso de la iteración sobre la matriz $a$ junto con los cálculos de $d$.Y al final no es difícil restablecer la subsecuencia deseada utilizando estas matrices.

  Solución en $O(n \log n)$ con estructuras de datos

  En lugar del método anterior para calcular la subsecuencia creciente más larga en $O(n \log n)$ también podemos resolver el problema de una manera diferente: utilizando algunas estructuras de datos simples.

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

  Por tanto, si definimos un array adicional $t$ tal que $$t] = d,$$entonces el problema de calcular el valor $d$ es equivalente a encontrar el valor máximo de un prefijo del array $t$:$$d = \\\Nmáximo de un prefijo de un array (que cambia) es un problema estándar que se puede resolver con muchas estructuras de datos diferentes. Por ejemplo, podemos utilizar un árbol de segmentos o un árbol de Fenwick.

  Este método tiene obviamente algunas deficiencias:en términos de longitud y complejidad de la implementación este enfoque será peor que el método que utiliza la búsqueda binaria.Además, si los números de entrada $a$ son especialmente grandes, entonces tendríamos que utilizar algunos trucos, como comprimir los números (es decir, renumerarlos de $0$ a $n-1$), o utilizar un árbol de segmentos implícito (sólo generar las ramas del árbol que son importantes).De lo contrario, 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 ninguna propiedad complicada en la solución de programación dinámica.Y este enfoque nos permite generalizar el problema muy fácilmente (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

  Este es de hecho casi el mismo problema.Sólo que ahora se permite usar números idénticos en la subsecuencia.

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

  Número de subsecuencias crecientes más largas

  Podemos utilizar el primer método discutido, ya sea la versión $O(n^2)$ o la versión que utiliza estructuras de datos.Sólo tenemos que almacenar adicionalmente de cuántas maneras podemos obtener subsecuencias crecientes más largas que terminen en los valores $d$.

  El número de maneras de formar una subsecuencia creciente más larga que termine en $a$ es la suma de todas las maneras para todas las subsecuencias crecientes más largas que terminen en $j$ donde $d$ sea máxima.Puede haber múltiples tales $j$, por lo que necesitamos sumarlos todos.

  Usando un árbol de segmentos este enfoque también puede implementarse en $O(n \log n)$.

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

  Mínimo número de subsecuencias no crecientes que cubren una secuencia

  Para una matriz dada con $n$ números $a$ tenemos que colorear los números en el menor número de colores, de manera que cada color forme una subsecuencia no creciente.

  Para resolverlo, observamos que el número mínimo de colores necesarios es igual a la longitud de la subsecuencia creciente más larga.

  Prueba:Necesitamos 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.Necesitamos demostrar que $x = y$.

  Es evidente que $y < x$ no es posible, porque si tenemos $x$ elementos estrictamente crecientes, entonces no hay dos que puedan formar parte de la misma subsecuencia no creciente.Por lo tanto tenemos $y \ge x$.

  Demostramos ahora 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 manera: siempre que haya dos subsecuencias tales que la primera comience antes que la segunda, y la primera secuencia comience con un número mayor o igual que la segunda, entonces desenganchamos este número inicial y lo unimos al comienzo de la segunda.Después de un número finito de pasos tenemos $y$ subsecuencias, y sus números de inicio formarán una subsecuencia creciente de longitud $y$.Como suponemos que $y > x$ llegamos a una contradicción.

  Por lo tanto se deduce que $y = x$.

  Restauración de las secuencias:La partición deseada de la secuencia en subsecuencias se puede hacer de forma codiciosa.Es decir, ir de izquierda a derecha y asignar el número actual o aquella subsecuencia que termine con el número mínimo que sea mayor o igual que el actual.

  Problemas prácticos

  • Topcoder – IntegerSequence
  • Topcoder – AutoMarket
  • Codeforces – Tourist
  • Codeforces – LCIS
  • SPOJ – SUPPER
  • Topcoder – BridgeArrangement
  • ACMSGURU – «North-East»
  (c) 2014-2021 translation by http://github.com/e-maxx-eng