Maximum Subarray

+10

Recibes una lista de números enteros nums. Un subarreglo es un tramo de elementos vecinos tomado sin saltos, y debe contener al menos un elemento. Devuelve la suma más grande que pueda tener cualquier subarreglo de nums. Devuelve solo la suma, no el subarreglo en sí.

Función

maxSubArray(nums: integer-array) → integer

numsinteger-array: la lista de números enteros, con al menos un elemento
Devuelveinteger: la suma más grande de una secuencia no vacía de elementos vecinos

Restricciones

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴
La respuesta siempre cabe en un entero con signo de 32 bits.

Ejemplos

Entrada: nums = [2, -4, 3, -1, 5, -6, 1]
Salida: 7
Explicación: La secuencia [3, -1, 5] suma 7. Extenderla hacia la izquierda añade -4 y después 2, una pérdida neta de 2. Extenderla hacia la derecha añade -6 y después 1, una pérdida neta de 5. Ninguna otra secuencia obtiene un resultado mejor.

Para ir más allá

¿También puedes resolverlo mediante divide y vencerás en O(n log n), dividiendo la lista por la mitad y procesando las secuencias que atraviesan el centro?

Solución

Una lista de n números tiene aproximadamente n²/2 subarreglos, demasiados para comprobarlos uno por uno cuando hay 10^5 elementos. La parte difícil son los números negativos: un tramo debe conservar un elemento negativo cuando lo que viene después lo compensa, y descartar todo lo anterior cuando no lo hace. El algoritmo de Kadane toma esa decisión en cada elemento con una sola comparación.

Suma cada subarreglo

Correcto, pero no termina con las pruebas más grandes

Intuición

Cada subarreglo tiene un primer índice left y un último índice right, así que probar cada par permite encontrar el mejor. Fija left y avanza right, sumando cada elemento nuevo a un total acumulado: cada subarreglo requiere una suma, sin un tercer bucle.

Aun así, quedan alrededor de n²/2 pares, cinco mil millones de sumas para 10^5 elementos.

Algoritmo

Asigna el primer elemento a best.
Para cada índice inicial left, establece total en 0.
Desplaza right desde left hasta el final de la lista y suma nums[right] a total.
Después de cada suma, guarda total en best si es mayor.
Devuelve best.

def maxSubArray(nums):
    best = nums[0]
    for left in range(len(nums)):
        total = 0
        # Grow the subarray that starts at left by one element at a time
        for right in range(left, len(nums)):
            total += nums[right]
            best = max(best, total)
    return best

Algoritmo de Kadane

Intuición

La mejor secuencia que termina en el índice i es solo nums[i], o la mejor secuencia que termina en i-1 con nums[i] añadido, ya que ninguna otra secuencia que termina en i-1 tiene una suma mayor. Así que conserva un número, endingHere, que representa la mejor suma de una secuencia que termina en el elemento actual. En el siguiente elemento x, se convierte en el mayor entre x y endingHere + x: mientras la suma de la secuencia sea positiva, la amplías, y cuando sea cero o negativa, empiezas de nuevo con x.

El mejor subarreglo termina en algún punto, así que la respuesta es el mayor valor que alcanza endingHere. En el primer ejemplo, toma los valores 2, -2, 3, 2, 7, 1, 2, y la respuesta es 7.

Algoritmo

Establece endingHere y best en el primer elemento.
Para cada elemento siguiente x, establece endingHere en el mayor entre x y endingHere + x.
Establece best en el mayor entre best y endingHere.
Después del último elemento, devuelve best.

def maxSubArray(nums):
    current = nums[0]
    best = nums[0]
    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])
        best = max(best, current)
    return best

Errores comunes y casos límite

Empezar best en 0. [-3, -1, -2] devuelve 0 en lugar de -1. Empieza desde el primer elemento.
Limitar la suma acumulada con max(0, endingHere + x). Falla con la misma lista; compara con x en su lugar.
Sumar solo los números positivos. Los elementos deben ser vecinos, así que el primer ejemplo da 7, no 2 + 3 + 5 + 1 = 11.
Empezar el bucle en el índice 1 sin establecer endingHere y best en nums[0]. Una lista de un solo elemento, como [-5], debe devolver -5.

Preguntas frecuentes3

¿Qué es el algoritmo de Kadane?

El algoritmo de Kadane encuentra la suma más grande de un subarreglo contiguo en una sola pasada. Mantiene la mejor suma de un segmento que termina en el elemento actual y, con cada elemento nuevo, extiende ese segmento o empieza uno nuevo. La mayor de estas sumas es la respuesta.

¿Cuál es la complejidad temporal del subarreglo máximo?

El algoritmo de Kadane tarda O(n) y usa O(1) de espacio adicional, porque cada elemento se examina una sola vez. Revisar cada subarray con una suma acumulada tarda O(n²), y sumar cada subarray desde cero tarda O(n³).

¿Por qué el subarreglo máximo es un problema de programación dinámica?

La mejor suma de una secuencia que termina en el índice i depende únicamente de la mejor suma de una secuencia que termina en i-1. Es decir, se trata de una recurrencia sobre los índices, la estructura de la programación dinámica. El algoritmo de Kadane conserva solo el valor más reciente en lugar de una tabla completa, por lo que necesita O(1) espacio.

def maxSubArray(nums):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumento

nums = [2, -4, 3, -1, 5, -6, 1]

Salida Esperada