Algoritmo di Kadence: sottoarray contiguo a somma più grande
Sara Chen
Qual è il sottoarray contiguo con la somma più grande?
Un sottoarray è una parte continua di un array. Può essere un singolo elemento di un array o una frazione dell'array. Il sottoarray contiguo con la somma più grande indica un sottoarray che ha il valore della somma massima.
Ad esempio, un array è {-10, 5, 1, 6, -9, 2, -7, 3, -5}. I suoi sottoarray possono essere: {-10,5,1,6} o {5,1,6} o {2,7,3, -5} ecc. Ma {5,1,6,3} non può essere un sottoarray perché non mantengono le sequenze.
Se noti, tra tutti i sottoarray, il sottoarray evidenziato seguente (5,1,6) ha il valore di sommatoria massimo:
La somma del sottoarray {5,1,6} = 11, è la somma massima in tutte le possibili combinazioni di sottoarray dell'array precedente. Quindi, per l'array precedente, il sottoarray massimo è {5,1,6}.
Algoritmo di Kadence: sottoarray contiguo a somma più grande
Approccio semplice per risolvere il sottoarray contiguo con la somma più grande
Il modo più semplice per risolvere questo problema è utilizzare due cicli per trovare tutti i sottoarray, calcolare la somma e quindi trovare il suo valore massimo.
Ecco il diagramma di flusso per l'approccio semplice per trovare il sottoarray contiguo con la somma più grande. Questo è un approccio di forza bruta, poiché stiamo esaminando tutti i possibili sottoarray.
Ecco i semplici passaggi per farlo.
Passo 1) Inizializza max_sum con il valore intero minimo e assegna le variabili "begin" e "end" con zero.
Passo 2) Sia i e j l'indice dell'array, dove “j” è maggiore che uguale a “i”. Rappresenta l'indice iniziale del sottoarray e "j" rappresenta l'indice finale del sottoarray.
Passo 3) "Current_sum" conterrà la somma del sottoarray. Dopo aver calcolato la somma corrente, controlla se current_sum è maggiore di max_sum.
Passo 4) Se current_sum è maggiore, sostituisci max_sum con la somma corrente.
Passo 5) Controlla se "j" raggiunge la fine dell'array o meno. Se "j" raggiunge la fine dell'array, incrementare "i" e modificare il valore current_sum su 0.
Passo 6) Esegui tutti questi passaggi finché "i" non raggiunge la fine dell'array.
Passo 7) Alla fine di questi due cicli, max_sum conterrà la somma del sottoarray più grande.
Pseudo codice per l'approccio semplice
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++ Attuazione dell'approccio semplice
#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]));
}
Produzione:
largest sum is 12 largest sum contiguous subarray: 5 1 6
Python Implementazione dell'approccio semplice
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)
Produzione:
largest sum is 12 largest sum contiguous subarray: 5 1 6
Algoritmo di Kadane per trovare il sottoarray contiguo con la somma più grande
L'algoritmo di Kadane è una sorta di metodo di “programmazione dinamica”. Qui useremo un ciclo invece di due cicli. L'implementazione generale dell'algoritmo di Kadane funziona solo per matrici di numeri positivi.
Abbiamo solo bisogno di due variabili per trovare il sottoarray contiguo con la somma più grande. Ecco il diagramma di flusso dell'algoritmo di Kadane:
Ecco i passaggi per l'algoritmo di Kadane:
Passo 1) Crea due variabili, current_sum e max_sum.
"Current_sum" manterrà il valore della somma massima che termina con un indice di array specifico, mentre "max_sum" memorizzerà il valore massimo della somma fino a quel momento.
Passo 2) Aggiungeremo il valore con current_sum per ogni elemento dell'array. Quindi controlleremo due condizioni di seguito:
- Se current_sum è inferiore all'elemento corrente, il valore current_sum sarà l'elemento corrente.
- Se max_sum è inferiore a current_sum, max_sum sarà current_sum.
Passo 3) Eseguendo il passaggio precedente per l'intero array, avremo la somma più grande del sottoarray contiguo nella variabile “max_sum”.
Esempio dell'algoritmo di Kadane
Dimostreremo l'algoritmo di Kadanes con un array di piccole dimensioni e discuteremo ogni passaggio per trovare il sottoarray contiguo con la somma più grande.
Supponiamo che l'array dato sia simile al seguente:
Ecco i passaggi dell'algoritmo di Kadane:
Passo 1) Crea due variabili, current_sum e max_sum. Assegna INT_MIN a max_sum e zero a current_sum. (Qui, INT_MIN indica il numero intero minimo).
Passo 2) All'indice 0, il valore è 4. Quindi, current_sum = 0 + 4 o 4. Qui current_sum è maggiore di max_sum, max_sum sarà 4.
Passo 3) All'indice 1, il valore è -2. Quindi, somma_corrente = 4 + (-2) o 2.
Questa volta current_sum è inferiore a max_sum. Di conseguenza, il valore di max_sum non verrà aggiornato.
Passo 4) Il valore successivo è 1. Se lo aggiungiamo con current_sum, current_sum sarà 3. Tuttavia, max_sum è maggiore di current_sum. Pertanto, max_sum non verrà aggiornato.
Passo 5) All'indice 3, il valore è tre. Aggiorneremo il valore incrementando current_sum di 3. Quindi, current_sum sarà 6.
In questo caso, max_sum è inferiore a current_sum. Quindi, max_sum verrà aggiornato con il valore di current_sum.
Passo 6) Per l'ultimo elemento dell'array abbiamo -1. Se lo aggiungiamo a current_sum, current_sum sarà 5, che è inferiore a max_sum. Quindi, max_sum rimarrà 6.
Quando raggiungiamo la fine dell'array, l'algoritmo termina qui. Ora, "max_sum" contiene il sottoarray della somma massima. Che è 5. Il sottoarray è {4,-2,1,3}.
Pseudo codice per l'algoritmo di 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++Implementazione dell'algoritmo di 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]));
}
Produzione:
largest sum is 12
Python Implementazione dell'algoritmo di 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])
Produzione:
largest sum is 12
Analisi della complessità per il sottoarray contiguo della somma più grande
L'approccio semplice utilizza due cicli. Questo metodo calcola tutte le possibili somme dei sottoarray per trovare quella più grande. È un approccio di forza bruta. Ogni ciclo viene eseguito fino alla fine del schieramento.
Se un array ha un totale di N elementi, quindi utilizzando due cicli, passeremo attraverso N2 elementi. Di conseguenza, la complessità temporale per un approccio semplice per trovare il sottoarray contiguo a somma più grande sarà O(N2). Qui, "O" indica la funzione di complessità.
D'altra parte, l'algoritmo di Kadane è il metodo di programmazione dinamica per trovare il massimo sottoarray di somma contigua. Se segui l'esempio o il codice, vedrai che stiamo utilizzando un solo ciclo.
Di conseguenza, se l'array di input ha una dimensione di N, allora la complessità temporale dell'algoritmo di Kadane sarà O(N). Questo è più veloce dell'approccio semplice. Ad esempio, un array contenente 100 elementi. L'approccio semplice richiederà 100*100 o 10,000 tempo CPU. Ma l'algoritmo di Kadane richiederà solo 100 tempo CPU.
