Algoritmo de Kadence: subconjunto contiguo de suma más grande
sarah chen
¿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.
Si observa, entre todos los subconjuntos, el siguiente subconjunto resaltado (5,1,6) tiene el valor de suma máximo:
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.
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
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 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:
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 siguiente:
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.
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á.
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á.
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.
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.
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
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 -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
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 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, la complejidad temporal de un enfoque simple para encontrar la suma más grande de subconjuntos contiguos será O(N2). Aquí, “O” significa la función de complejidad.
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 la complejidad temporal 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 tomará 100*100 o 10,000 100 veces el tiempo de CPU. Pero el algoritmo de Kadane tomará solo XNUMX veces el tiempo de CPU.
