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

¿Cuál es el subarreglo contiguo de suma más grande?

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, una matriz es {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Sus submatrices pueden ser: {-10,5,1,6} o {5,1,6} o {2,7,3, -5} etc. Pero {5,1,6,3} no puede ser un subarreglo porque no mantienen las secuencias.

Subarreglo contiguo de suma más grande

Si notas, entre todos los subarreglos, siguewing el subarreglo resaltado (5,1,6) tiene el valor de suma máximo:

Subarreglo contiguo de suma más grande

La suma del subarreglo {5,1,6} = 11, es la suma máxima en todas las combinaciones posibles de subarreglo del arreglo anterior. Entonces, para la matriz anterior, el subarreglo máximo es {5,1,6}.

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

Enfoque simple para resolver el subarreglo contiguo de suma más grande

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.

A continuación se muestra el diagrama de flujo del método sencillo para encontrar el subconjunto contiguo de suma más grande. Este es un enfoque de fuerza bruta, ya que analizamos todos los subarreglos posibles.

Enfoque simple para resolver la suma más grande

Estos son los sencillos pasos para hacer esto.

Paso 1) Inicialice max_sum con un valor entero mínimo y asigne las variables "comienzo" y "fin" con cero.

Paso 2) Sean i y j el índice de la matriz, donde "j" es mayor que "i". Representa el índice inicial del subarreglo y "j" representa el índice final del subarreglo.

Paso 3) "Current_sum" contendrá la suma del subarreglo. Después de calcular la suma actual, verifique si current_sum es mayor que max_sum.

Paso 4) Si current_sum es mayor, reemplace max_sum con la suma actual.

Paso 5) Compruebe si "j" llega al final de la matriz o no. Si "j" llega al final de la matriz, entonces incremente "i" y cambie el valor de current_sum a 0.

Paso 6) Realice todos estos pasos hasta que "i" llegue al final de la matriz.

Paso 7) Al final de estos dos bucles, max_sum contendrá la suma de subarreglo más grande.

Pseudocódigo para un enfoque simple

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

Implementación de C++ 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

Implementación de Python 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 el subarreglo contiguo de suma más grande

El algoritmo de Kadane es una especie de método de "programación dinámica". Aquí usaremos un bucle en lugar de dos bucles. La implementación general del algoritmo de Kadane solo funciona para matrices de números positivos.

Solo necesitamos dos variables para encontrar el subarreglo contiguo de suma más grande. Aquí está el diagrama de flujo del algoritmo de Kadane:

Algoritmo de Kadane para encontrar la suma más grande

Estos son los pasos para el algoritmo de Kadane:

Paso 1) Cree dos variables, suma_actual y suma_máx.

“Current_sum” mantendrá el valor de la suma máxima que termina en un índice de matriz específico, mientras que “max_sum” almacenará el valor de suma máxima hasta el momento.

Paso 2) Agregaremos el valor con current_sum para cada elemento de la matriz. Luego verificaremos dos condiciones a continuación:

  • Si current_sum es menor que el elemento actual, entonces el valor current_sum será el elemento actual.
  • Si suma_max es menor que suma_actual, entonces suma_max será suma_actual.

Paso 3) Realizando el paso anterior para todo el arreglo, tendremos el subarreglo contiguo de suma más grande en la variable “max_sum”.

Ejemplo del algoritmo de Kadane

Demostraremos el algoritmo de Kadanes con una matriz de tamaño pequeño y discutiremos cada paso para encontrar la submatriz contigua de suma más grande.

Supongamos que la matriz dada es como la siguientewing:

Ejemplo del algoritmo de Kadane

Estos son los pasos del algoritmo de Kadane:

Paso 1) Cree dos variables, suma_actual y suma_máx. Asigne INT_MIN a max_sum y cero a current_sum. (Aquí, INT_MIN significa el número entero mínimo).

Paso 2) En el índice 0, el valor es 4. Entonces, current_sum = 0 + 4 o 4. Aquí current_sum es mayor que max_sum, max_sum será 4.

Ejemplo del algoritmo de Kadane

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

Esta vez la suma_actual es menor que la suma_máxima. Como resultado, el valor de max_sum no se actualizará.

Ejemplo del algoritmo de Kadane

Paso 4) El siguiente valor es 1. Si sumamos esto con la suma_actual, entonces la suma_actual será 3. Aún así, la suma_máxima es mayor que la suma_actual. Por lo tanto, max_sum no se actualizará.

Ejemplo del algoritmo de Kadane

Paso 5) En el índice 3, el valor es tres. Actualizaremos el valor incrementando la suma_actual en 3. Entonces, la suma_actual será 6.

Ejemplo del algoritmo de Kadane

En este caso, max_sum es menor que current_sum. Entonces, max_sum se actualizará con el valor de current_sum.

Paso 6) Para el último elemento de la matriz, tenemos -1. Si agregamos esto con current_sum, current_sum será 5, que es más pequeño que max_sum. Entonces, max_sum seguirá siendo 6.

Ejemplo del algoritmo de Kadane

Cuando llegamos al final de la matriz, el algoritmo termina aquí. Ahora, "max_sum" contiene el subarreglo de suma máxima. Que es 5. El subarreglo es {4,-2,1,3}.

Pseudocódigo para el algoritmo de Kadane

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each elements 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

Implementación en C++ 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 -10000000
  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

Implementación en Python 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

¿CómoplexAnálisis de ciudad para el subarreglo contiguo de suma más grande

El método simple utiliza dos bucles. Ese método calcula todas las sumas posibles de subarreglos para encontrar el más grande. Es un enfoque de fuerza bruta. Cada bucle se ejecuta hasta el final del matriz.

Si una matriz tiene un total de N elementos, luego usando dos bucles, pasaremos por N2 elementos. Como resultado, el tiempo complexLa ventaja de un enfoque simple para encontrar el subarreglo contiguo de suma más grande será O(N2). Aquí, "O" significa la complexfunción de idad.

Por otro lado, el algoritmo de Kadane es el método de programación dinámica para encontrar el subarreglo de suma contiguo máximo. Si sigues el ejemplo o el código, verás que estamos usando solo un bucle.

Como resultado, si la matriz de entrada tiene un tamaño de N, entonces el tiempo complexLa calidad del algoritmo de Kadane será O (N). Esto es más rápido que el enfoque simple. Por ejemplo, una matriz que contiene 100 elementos. El enfoque simple requerirá 100*100 o 10,000 tiempos de CPU. Pero el algoritmo de Kadane requerirá sólo 100 CPU.