Buscar el subarreglo con suma máxima/mínima

Aquí consideramos el problema de hallar un subarreglo con suma máxima, así como algunas de sus variantes (incluyendo el algoritmo para resolver este problema online).

Enunciado del problema

Se da un arreglo de números $a[1 \ldots n]$. Se pide hallar un subarreglo $a[l \ldots r]$ con la suma máxima:

$$\max_{ 1 \le l \le r \le n } \sum_{i=l}^{r} a[i].$$

Por ejemplo, si todos los enteros del arreglo $a[]$ fueran no negativos, entonces la respuesta sería el arreglo mismo. Sin embargo, la solución no es trivial cuando el arreglo puede contener tanto números positivos como negativos.

Está claro que el problema de hallar el subarreglo mínimo es esencialmente el mismo: solo hay que cambiar los signos de todos los números.

Algoritmo 1

Aquí consideramos un algoritmo casi obvio. (A continuación veremos otro algoritmo, que es un poco más difícil de idear, pero su implementación es aún más corta.)

Descripción del algoritmo

El algoritmo es muy sencillo.

Introducimos por conveniencia la notación: $s[i] = \sum_{j=1}^{i} a[j]$. Es decir, el arreglo $s[i]$ es un arreglo de sumas parciales del arreglo $a[]$. También, ponemos $s[0] = 0$.

Iteremos ahora sobre el índice $r = 1 \ldots n$, y aprendamos a hallar rápidamente el $l$ óptimo para cada valor actual $r$, en el que se alcanza la suma máxima en el subarreglo $[l, r]$.

Formalmente, esto significa que para el $r$ actual necesitamos hallar un $l$ (que no exceda $r$), de modo que el valor de $s[r] - s[l-1]$ sea máximo. Tras una transformación trivial, podemos ver que necesitamos hallar en el arreglo $s[]$ un mínimo en el segmento $[0, r-1]$.

De aquí obtenemos de inmediato una solución: simplemente guardamos dónde está el mínimo actual en el arreglo $s[]$. Usando este mínimo, hallamos el índice óptimo actual $l$ en $O(1)$, y al pasar del índice actual $r$ al siguiente, simplemente actualizamos este mínimo.

Obviamente, este algoritmo funciona en $O(n)$ y es asintóticamente óptimo.

Implementación

Para implementarlo, ni siquiera necesitamos guardar explícitamente un arreglo de sumas parciales $s[]$: solo necesitaremos el elemento actual de él.

La implementación se da en arreglos con indexación desde cero, no en numeración desde uno como se describió arriba.

Primero damos una solución que halla una respuesta numérica simple sin hallar los índices del segmento deseado:

int ans = a[0], sum = 0, min_sum = 0;
 
for (int r = 0; r < n; ++r) {
    sum += a[r];
    ans = max(ans, sum - min_sum);
    min_sum = min(min_sum, sum);
}

Ahora damos una versión completa de la solución, que además también halla los límites del segmento deseado:

int ans = a[0], ans_l = 0, ans_r = 0;
int sum = 0, min_sum = 0, min_pos = -1;
 
for (int r = 0; r < n; ++r) {
    sum += a[r];
    int cur = sum - min_sum;
    if (cur > ans) {
        ans = cur;
        ans_l = min_pos + 1;
        ans_r = r;
    }
    if (sum < min_sum) {
        min_sum = sum;
        min_pos = r;
    }
}

Algoritmo 2

Aquí consideramos un algoritmo distinto. Es un poco más difícil de entender, pero es más elegante que el de arriba, y su implementación es un poco más corta. Este algoritmo lo propuso Jay Kadane en 1984.

Descripción del algoritmo

El algoritmo en sí es el siguiente. Recorremos el arreglo y acumulamos la suma parcial actual en alguna variable $s$. Si en algún momento $s$ es negativa, simplemente asignamos $s=0$. Se afirma que el máximo de todos los valores que se asignan a la variable $s$ durante el algoritmo será la respuesta al problema.

Demostración:

Consideremos el primer índice cuando la suma $s$ se vuelve negativa. Esto significa que empezando con una suma parcial cero, eventualmente obtenemos una suma parcial negativa: así que todo este prefijo del arreglo, así como cualquier sufijo, tiene suma negativa. Por lo tanto, este subarreglo nunca contribuye a la suma parcial de ningún subarreglo del que sea prefijo, y se puede simplemente descartar.

Sin embargo, esto no basta para demostrar el algoritmo. En el algoritmo, de hecho estamos limitados a hallar la respuesta solo en aquellos segmentos que empiezan inmediatamente después de los lugares en que ocurrió $s<0$.

Pero, de hecho, consideremos un segmento arbitrario $[l, r]$, y $l$ no está en tal posición “crítica” (es decir, $l > p+1$, donde $p$ es la última tal posición en la que $s<0$). Como la última posición crítica es estrictamente anterior a $l-1$, resulta que la suma de $a[p+1 \ldots l-1]$ es no negativa. Esto significa que al mover $l$ a la posición $p+1$, aumentaremos la respuesta o, en casos extremos, no la cambiaremos.

De una u otra forma, resulta que al buscar una respuesta, uno puede limitarse solo a segmentos que empiezan inmediatamente después de las posiciones en las que apareció $s<0$. Esto demuestra que el algoritmo es correcto.

Implementación

Como en el algoritmo 1, primero dimos una implementación simplificada que busca solo una respuesta numérica sin hallar los límites del segmento deseado:

int ans = a[0], sum = 0;
 
for (int r = 0; r < n; ++r) {
    sum += a[r];
    ans = max(ans, sum);
    sum = max(sum, 0);
}

Una solución completa, que mantiene los índices de los límites del segmento correspondiente:

int ans = a[0], ans_l = 0, ans_r = 0;
int sum = 0, minus_pos = -1;
 
for (int r = 0; r < n; ++r) {
    sum += a[r];
    if (sum > ans) {
        ans = sum;
        ans_l = minus_pos + 1;
        ans_r = r;
    }
    if (sum < 0) {
        sum = 0;
        minus_pos = r;
    }
}

Tareas relacionadas

Hallar el subarreglo máximo/mínimo con restricciones

Si la condición del problema impone restricciones adicionales sobre el segmento pedido $[l, r]$ (por ejemplo, que la longitud $r-l+1$ del segmento debe estar dentro de los límites especificados), entonces el algoritmo descrito probablemente se generalizará fácilmente a estos casos: de todos modos, el problema seguirá siendo hallar el mínimo en el arreglo $s[]$ con las restricciones adicionales especificadas.

Caso bidimensional del problema: búsqueda de submatriz máxima/mínima

El problema descrito en este artículo se generaliza de forma natural a dimensiones mayores. Por ejemplo, en un caso bidimensional, se convierte en la búsqueda de una submatriz $[l_1 \ldots r_1, l_2 \ldots r_2]$ de una matriz dada, que tenga la suma máxima de números en ella.

Usando la solución del caso unidimensional, es fácil obtener una solución en $O(n^3)$ para el caso bidimensional: iteramos sobre todos los valores posibles de $l_1$ y $r_1$, y calculamos las sumas de $l_1$ a $r_1$ en cada fila de la matriz. Ahora tenemos el problema unidimensional de hallar los índices $l_2$ y $r_2$ en este arreglo, que ya se puede resolver en tiempo lineal.

Se conocen algoritmos más rápidos para resolver este problema, pero no son mucho más rápidos que $O(n^3)$, y son muy complejos (tan complejos que muchos de ellos son inferiores al algoritmo trivial para todas las restricciones razonables por la constante oculta). Actualmente, el mejor algoritmo conocido funciona en tiempo $O\left(n^3 \frac{ \log^3 \log n }{ \log^2 n} \right)$ (T. Chan 2007 “More algorithms for all-pairs shortest paths in weighted graphs”)

Este algoritmo de Chan, así como muchos otros resultados en esta área, de hecho describen multiplicación rápida de matrices (donde multiplicación de matrices significa multiplicación modificada: se usa el mínimo en lugar de la suma, y la suma en lugar de la multiplicación). El problema de hallar la submatriz con la mayor suma se puede reducir al problema de hallar los caminos más cortos entre todos los pares de vértices, y este problema, a su vez, se puede reducir a tal multiplicación de matrices.

Búsqueda de un subarreglo con promedio máximo/mínimo

Este problema consiste en hallar un segmento $a[l, r]$ tal que el valor promedio sea máximo:

$$\max_{l \le r} \frac{ 1 }{ r-l+1 } \sum_{i=l}^{r} a[i].$$

Por supuesto, si no se imponen otras condiciones sobre el segmento pedido $[l, r]$, entonces la solución siempre será un segmento de longitud $1$ en el elemento máximo del arreglo. El problema solo tiene sentido si hay restricciones adicionales (por ejemplo, la longitud del segmento deseado está acotada por abajo).

En este caso, aplicamos la técnica estándar al trabajar con problemas del valor promedio: seleccionaremos el valor promedio máximo deseado mediante búsqueda binaria.

Para ello, necesitamos aprender a resolver el siguiente subproblema: se da el número $x$, y necesitamos comprobar si existe un subarreglo del arreglo $a[]$ (por supuesto, que satisfaga todas las restricciones adicionales del problema), donde el valor promedio es mayor que $x$.

Para resolver este subproblema, restamos $x$ de cada elemento del arreglo $a[]$. Entonces nuestro subproblema de hecho se convierte en este: si hay o no subarreglos de suma positiva en este arreglo. Y ya sabemos cómo resolver este problema.

Así, obtuvimos la solución para la cota asintótica $O(T(n) \log W)$, donde $W$ es la precisión pedida, $T(n)$ es el tiempo de resolver la subtarea para un arreglo de longitud $n$ (que puede variar según las restricciones adicionales concretas impuestas).

Resolver el problema online

La condición del problema es la siguiente: se da un arreglo de $n$ números, y un número $L$. Hay consultas de la forma $(l,r)$, y en respuesta a cada consulta, se pide hallar un subarreglo del segmento $[l, r]$ de longitud no menor que $L$ con la media aritmética máxima posible.

El algoritmo para resolver este problema es bastante complejo. KADR (Yaroslav Tverdokhleb) describió su algoritmo en el foro ruso .