El Algoritmo de Kadane explicado

#algoritmos #matrices #kadane #suma

Un problema común en programación es el de encontrar la suma máxima de números consecutivos dentro de una matriz unidimensional (también llamada vector o arreglo).

Es decir, si tenemos:

[2, -3, 2, 2, 0]

Vemos claramente que la máxima suma de números consecutivos es 4, formada por los elementos de las posiciones 2 y 3. Descartamos la suma de los cuatro primeros elementos pues da como resultado 3 (2 + (-3) + 2 + 2 = 3), tampoco tomamos en cuenta la suma de las posiciones 1, 2 y 3 pues da como resultado 1 (-3 + 2 + 2 = 1). No podemos sumar las posiciones 0, 2 y 3 (2 + 2 + 2 = 6) porque no son consecutivas.

La solución

Como no siempre trabajaremos con matrices tan pequeñas, hay que buscar un método que nos ayude a hacerlo de manera óptima. Por suerte, el matemático estadounidense Joseph Born Kadane ya se lo ha pensado, y su solución hoy se conoce como Algoritmo de Kadane. Lo mejor de este algoritmo es que se ejecuta en tiempo lineal, es decir, el número de operaciones depende directamente del tamaño del problema (O(n)).

La idea detrás del algoritmo es encontrar la suma máxima de la submatriz cuyo último índice sea la posición en la que nos encontramos. Hay dos opciones: que la suma máxima hasta el índice en el que nos encontramos sea tal cual el elemento contenido en el índice donde nos encontramos, o que la suma máxima hasta el índice en el que nos encontramos sea el elemento contenido en el índice donde nos encontramos más la suma máxima de la submatriz cuyo último índice es el índice anterior. Damos por hecho que la máxima suma al inicio siempre será el valor del primer elemento de la matriz.

Suena algo confuso al principio, pero con un ejemplo quedará más claro.

El algoritmo paso a paso

Siguiendo la misma matriz que al principio, tenemos:

Posición	0	1	2	3	4
Elemento	2	-3	2	2	0

Primero, tanto nuestro valor máximo total como nuestro valor máximo actual deben ser iguales al elemento en la primera posición de la matriz (la posición 0), en este caso, igual a 2:

maximo_total = 2
maximo_actual = 2

Comenzando en la posición 1:

Posición	0	1	2	3	4
Elemento	2	-3	2	2	0

Hay que verificar qué es mayor: el elemento que se encuentra en esa posición o el elemento de esa posición más la máxima suma de la submatriz cuyo último elemento sea la posición anterior.

El elemento en la posición 1 es -3.

Como estamos empezando, la suma de la submatriz anterior que cumple la condición es el elemento en la posición 0, es decir 2. Y 2 + (-3) es igual a -1.

Ahora comparamos... ¿cuál es mayor? ¿-1 o -3? la respuesta es -1. -1 es el nuevo máximo actual.

Bien, ahora una nueva comparación. ¿Es el nuevo máximo actual mayor al máximo total? ¿-1 es mayor que 2? NO, entonces no hay cambios en el máximo total:

maximo_total = 2
maximo_actual = -1

En este punto "máximo_actual" no es otra cosa mas que esa confusa "máxima suma de la submatriz cuyo último elemento sea la posición anterior". Detente un momento a pensarlo.

Vamos a la siguiente posición, a la posición 2:

Posición	0	1	2	3	4
Elemento	2	-3	2	2	0

La suma del elemento de la posición actual más el máximo actual corresponde a 2 + (-1), que es igual a 1.

Ahora comparamos... ¿cuál es mayor? ¿2 o 1? la respuesta es 2. 2 es el nuevo máximo actual.

¿Es el nuevo máximo actual mayor al máximo total? ¿2 es mayor que 2? NO, entonces no hay cambios en el máximo total:

maximo_total = 2
maximo_actual = 2

Vamos a la siguiente posición, a la posición 3:

Posición	0	1	2	3	4
Elemento	2	-3	2	2	0

La suma del elemento de la posición actual más el máximo actual corresponde a 2 + 2, que es igual a 4.

Ahora comparamos... ¿cuál es mayor? ¿2 o 4? la respuesta es 4. 4 es el nuevo máximo actual.

¿Es el nuevo máximo actual mayor al máximo total? ¿4 es mayor que 2? SÍ, entonces máximo total es igual a 4:

maximo_total = 4
maximo_actual = 4

Vamos a la siguiente posición, a la posición 4 (y última):

Posición	0	1	2	3	4
Elemento	2	-3	2	2	0

La suma del elemento de la posición actual más el máximo actual corresponde a 0 + 4, que es igual a 4.

Ahora comparamos... ¿cuál es mayor? ¿4 o 4? ninguno, son iguales. El máximo actual se queda igual.

Y ya no queda más que recorrer, podemos regresar nuestro máximo total sabiendo que es la mayor suma de una submatriz dentro de la matriz.

Implementación en C++

Podemos representar el algoritmo con el siguiente código en C++, donde A[] es la matriz y N el tamaño de la misma:

int kadane(int A[], int N) {
    int maximo_total = A[0];
    int maximo_actual = A[0];

    for (int i = 1; i < N; i++) {
        maximo_actual = max(A[i], maximo_actual + A[i]);
        if (maximo_actual > maximo_total) {
            maximo_total = maximo_actual;
        }
    }

    return maximo_total;
}

Ventajas del algoritmo

La principal ventaja de usar este algoritmo para solucionar el problema, es su complejidad lineal O(n). Por ejemplo, el siguiente código también soluciona el problema, pero con una complejidad cuadrática O(n^2):

int solucionn2(int A[], int N) {
    int maximo_total = 0;
    for (int i = 0; i < N; i++) {
        int maximo_actual = 0;
        for (int j = i; j < N; j++) {
            maximo_actual += A[j];
            if (maximo_actual > maximo_total) {
                maximo_total = maximo_actual;
            }
        }
    }
    return maximo_total;
}

¿Qué tanto afecta eso? bueno, suponiendo que tenemos una computadora que ejecuta mil millones de instrucciones por segundo, el código del algoritmo de Kadane tardaría aproximadamente 0.10 segundos en procesar una matriz de 100,000,000 de elementos, mientras que el segundo código tardaría más de 115... días .-.

Espero que este post sea de ayuda a alguien.