Algoritmo de Kadence: subconjunto contiguo de suma más grande

¿Cuál es la submatriz contigua de mayor suma?

Un subarreglo es una parte continua de un arreglo. Puede ser un solo elemento de una matriz o alguna fracción de la matriz. El subarreglo contiguo de suma más grande significa un subarreglo que tiene el valor de suma máximo.

Por ejemplo, consideremos el arreglo {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Sus subarreglos pueden ser {-10, 5, 1, 6}, {5, 1, 6} o {2, -7, 3, -5}, y así sucesivamente. Sin embargo, {5, 1, 6, 3} no puede ser un subarreglo porque sus elementos no están en una secuencia contigua.

Si observas, entre todos los subconjuntos, el subconjunto resaltado {5, 1, 6} tiene el valor de suma máximo:

La suma del subarreglo {5, 1, 6} es 12, la suma máxima posible entre todos los subarreglos del arreglo anterior. Por lo tanto, para este arreglo, el subarreglo contiguo con la suma máxima es {5, 1, 6}.

Método sencillo para resolver el problema de la suma máxima en submatrices contiguas.

La forma sencilla de resolver este problema es utilizar dos bucles para encontrar todos los subarreglos, calcular la suma y luego encontrar su valor máximo.

Aquí se muestra el diagrama de flujo para el método sencillo de encontrar la submatriz contigua con la suma más grande. Este es un método de fuerza bruta, ya que recorremos todas las submatrices posibles.

Estos son los sencillos pasos para hacer esto.

Paso 1) Inicializar suma máxima con el valor entero mínimo y el conjunto begin y final a cero.

Paso 2) Deje que i y j ser índices de matriz donde j es mayor o igual que i; i marca el inicio del subconjunto y j su fin.

Paso 3) suma_actual contiene la suma acumulada. Después de cada actualización, compruebe si suma_actual es mayor que suma máxima.

Paso 4) If suma_actual es mayor, reemplazar suma máxima con ella.

Paso 5) Cuando j llega al final del array, incrementa i y reiniciar suma_actual a 0.

Paso 6) Repita hasta que i llega al final del array. suma máxima luego contiene la suma de submatrices más grande.

Apodo Code para un enfoque sencillo

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        store the maximum subArray
    return the maximum sum

C++ Implementación de un enfoque simple

#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
    int max_sum = -1e9;
    int begin = 0;
    int end = 0;
    for (int i = 0; i < n; i++) {
        int current_sum = 0;
        for (int j = i; j < n; j++) {
            current_sum += array[j];
            if (max_sum < current_sum) {
                max_sum = current_sum;
                begin = i;
                end = j;
            }
        }
    }
    cout << "largest sum is " << max_sum << endl;
    cout << "largest sum contiguous subarray: ";
    for (int i = begin; i <= end; i++) {
        cout << array[i] << "\t";
    }
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}

Salida:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Python Implementación de un enfoque simple

def maximumSubarraySum(numbers):
    max_sum, begin, end = -1e9, 0, 0
    for i in range(len(numbers)):
        current_sum = 0
        for j in range(i, len(numbers)):
            current_sum += numbers[j]
            if max_sum < current_sum:
                max_sum = current_sum
                begin, end = i, j
    print("largest sum is ", max_sum)
    print("largest sum contiguous subarray: ", end='')
    for i in range(begin, end + 1):
        print(numbers[i], end='\t')

numbers = [-10, 5, 1, 6, -9, 2, -7, 3, -5]
maximumSubarraySum(numbers)

Salida:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Algoritmo de Kadane para encontrar la submatriz contigua de suma más grande

El algoritmo de Kadane es un método de programación dinámica que utiliza un solo bucle en lugar de dos. Maneja arreglos con números positivos y negativos, siempre que al menos un valor sea no negativo.

Solo necesitamos dos variables para encontrar la submatriz contigua con la suma más grande. Aquí está el diagrama de flujo:

Estos son los pasos para el algoritmo de Kadane:

Paso 1) Crea dos variables, suma_actual y suma máxima.

suma_actual conserva la suma máxima que termina en un índice de matriz específico, mientras que suma máxima Almacena el mayor valor de suma observado hasta el momento.

Paso 2) Agregue cada elemento de la matriz a suma_actualA continuación, compruebe las dos condiciones siguientes:

• If suma_actual es menor que el elemento actual, entonces suma_actual se convierte en el elemento actual.
• If suma máxima es menor que suma_actual, luego suma máxima se convierte en suma_actual.

Paso 3) Después de repetir el paso anterior para todo el conjunto, suma máxima contiene la submatriz contigua de mayor suma.

Ejemplo del algoritmo de Kadane

Demostramos el algoritmo de Kadane en un arreglo pequeño y explicamos cada paso para encontrar el subarreglo contiguo con la suma más grande.

Supongamos que el arreglo dado es como el siguiente:

Estos son los pasos del algoritmo de Kadane:

Paso 1) Crea dos variables, suma_actual y suma máxima. Asignar INT_MIN a suma máxima y cero a suma_actualAquí, INT_MIN representa el valor entero mínimo.

Paso 2) En el índice 0, el valor es 4. Entonces, suma_actual = 0 + 4 = 4. Dado que suma_actual Es mas grande que suma máxima, suma máxima se convierte en 4.

Paso 3) En el índice 1, el valor es -2. Entonces, suma_actual = 4 + (-2) = 2.

Esta vez suma_actual es menor que suma máxima. Como resultado, el valor de suma máxima no está actualizado.

Paso 4) El siguiente valor es 1. Sumándolo a suma_actual da 3. Dado que suma máxima (4) sigue siendo mayor que suma_actual, suma máxima no está actualizado.

Paso 5) En el índice 3, el valor es 3. Incrementando suma_actual por 3 da suma_actual = 6.

En este caso, suma máxima es más pequeño que suma_actual, asi que suma máxima se actualiza con el valor de suma_actual.

Paso 6) Para el último elemento del array, tenemos -1. Sumándolo a suma_actual da 5, que es menor que suma máxima. Asi que, suma máxima quedan 6.

Al llegar al final del array, el algoritmo termina aquí. Ahora, suma máxima contiene la suma máxima, que es 6. El subconjunto es {4, -2, 1, 3}.

Apodo Code para el algoritmo de Kadane

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element in array:
        add the element with current_sum
        if current_sum is greater than the maximum_sum
            then maximum_sum = current_sum
        if current_sum is less than the element
            then current_sum = element
    return the value of maximum_sum

C++ Implementación del algoritmo de Kadane.

#include <iostream>
using namespace std;
void kadane(int array[], int n) {
    int current_sum = 0;
    int max_sum = -1e9;
    // -1e9 means -1,000,000,000
    for (int i = 0; i < n; i++) {
        current_sum += array[i];
        if (max_sum < current_sum) {
            max_sum = current_sum;
        }
        if (current_sum < array[i]) {
            current_sum = array[i];
        }
    }
    cout << "largest sum is " << max_sum << endl;
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    kadane(array, sizeof(array) / sizeof(array[0]));
}

Salida:

largest sum is 12

Python Implementación del algoritmo de Kadane.

def kadane(numbers):
    current_sum = 0
    max_sum = -1e9
    for i in range(len(numbers)):
        current_sum += numbers[i]
        if max_sum < current_sum:
            max_sum = current_sum
        if current_sum < numbers[i]:
            current_sum = numbers[i]
    print("largest sum is ", max_sum)

kadane([-10, 5, 1, 6, -9, 2, -7, 3, -5])

Salida:

largest sum is 12

Análisis de complejidad para el subarreglo contiguo de suma más grande

El enfoque simple utiliza dos bucles para calcular la suma de cada submatriz posible y localizar la mayor. Es un enfoque de fuerza bruta; cada bucle se ejecuta hasta el final de la matriz. matrizdando O(N²) en las transacciones.

El algoritmo de Kadane utiliza un solo bucle, lo que resulta en un tiempo de O(N) y un espacio adicional de O(1). En un arreglo de 100 elementos, el método simple realiza 100 × 100 = 10 000 operaciones, mientras que el de Kadane realiza solo 100, lo que supone una mejora drástica en la velocidad para entradas grandes.

Preguntas Frecuentes