Explicación del algoritmo de Kadane

Dado un arreglo, el algoritmo para encontrar la suma máxima del subarreglo se llama Algoritmo de Kadane. El arreglo puede ser de cualquier dimensión. Para simplificar, comencemos con una matriz 1D.

Tomemos una matriz indexada en 0:

arreglo: [5, 7, -3, 2, 9, 6, 16, 22, 21, 29, -14, 10, 12]

Podemos comenzar el subarreglo en cualquier punto. Digamos que comenzamos en el índice 2, es decir, arr[2] = -3. Ahora, en el índice 3, la suma será -3 + 2 = -1. Si comenzamos el subarreglo en el índice 3, la suma en el índice 3 es 2, que es mayor que la suma anterior.

Así que tenemos dos opciones: comenzar en el índice actual o agregar el elemento actual a la suma anterior.

Y dado que queremos la suma máxima del subarreglo, agregamos el elemento actual al máximo de 0 y la suma anterior (cero aquí indica que estamos comenzando de nuevo desde el elemento actual).

Este problema cae bajo el Paradigma de Programación Dinámica.

Tomemos un arreglo dp[] donde cada dp[i] denota la suma máxima del subarreglo que termina en el índice i (incluido i).

Podemos decir eso

Condiciones base: dp[0] = arr[0]

Respuesta:Un elemento máximo en la matriz dp[]

Complejidad de tiempo: O(N)Complejidad de espacio: O(N)

Podríamos optimizar la complejidad del espacio tomando dp[i-1], que es la suma anterior en una variable, eliminando la necesidad de una matriz dp[].

Complejidad de tiempo: O(N)Complejidad de espacio: O(1)

También podríamos encontrar los índices del subarreglo que tiene la suma máxima.

También podríamos aplicar Kadane a la matriz 2D, donde tenemos que encontrar la suma máxima de la submatriz. Siéntase libre de probar kadane para matrices 2D. ¡Gracias por leer! 😃