Kadence's Algorithm: Största summa sammanhängande subarray
Sarah Chen
Vilken är den största summan sammanhängande subarrayen?
En subarray är en kontinuerlig del av en array. Det kan vara ett enstaka element i en array eller en del av arrayen. Den största summan sammanhängande delmatrisen betyder en delmatris som har det maximala summavärdet.
Till exempel är en matris {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Dess undermatriser kan vara: {-10,5,1,6} eller {5,1,6} eller {2,7,3, -5} etc. Men {5,1,6,3} kan inte vara en subarray eftersom de inte underhåller sekvenserna.
Om du märker, bland alla underarrayer, har följande markerade underarray (5,1,6) det maximala summeringsvärdet:
Summan av delmatrisen {5,1,6} = 11, är den maximala summan i alla möjliga kombinationer av delmatrisen i ovanstående matris. Så för ovanstående array är den maximala underarrayen {5,1,6}.
Kadence's Algorithm: Största summa sammanhängande subarray
Enkelt tillvägagångssätt för att lösa den största summan sammanhängande subarrayen
Det enkla sättet att lösa detta problem är att använda två slingor för att hitta alla subarrayer, beräkna summan och sedan hitta dess maximala värde.
Här är flödesschemat för det enkla tillvägagångssättet för att hitta den största summan sammanhängande sub-arrayen. Det här är en brute force-strategi, eftersom vi går igenom alla möjliga subarrays.
Här är de enkla stegen för att göra detta.
Steg 1) Initiera max_summen med lägsta heltalsvärde och tilldela variablerna "begynn" och "slut" med noll.
Steg 2) Låt i och j vara indexet för arrayen, där "j" är större än lika med "i". Det representerar startindexet för subarrayen och "j" representerar subarrayens slutindex.
Steg 3) "Current_sum" kommer att hålla summan av subarrayen. Efter att ha beräknat den aktuella summan, kontrollera om aktuell_summa är större än max_summan.
Steg 4) Om aktuell_summa är större, ersätt sedan max_summan med den aktuella summan.
Steg 5) Kontrollera om "j" når slutet av arrayen eller inte. Om "j" når slutet av matrisen, öka sedan "i" och ändra värdet för aktuell_summa till 0.
Steg 6) Utför alla dessa steg tills "i" når slutet av arrayen.
Steg 7) I slutet av dessa två slingor kommer max_summan att innehålla den största delmatrissumman.
Pseudokod för enkel metod
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++ Implementering av Simple Approach
#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]));
}
Produktion:
largest sum is 12 largest sum contiguous subarray: 5 1 6
Python Implementering av enkelt tillvägagångssätt
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)
Produktion:
largest sum is 12 largest sum contiguous subarray: 5 1 6
Kadanes algoritm för att hitta den största summan sammanhängande subarray
Kadanes algoritm är en slags "dynamisk programmering"-metod. Här kommer vi att använda en slinga istället för två slingor. Allmän implementering av Kadanes algoritm fungerar endast för positiva talmatriser.
Vi behöver bara två variabler för att hitta den största summan sammanhängande subarrayen. Här är flödesschemat för Kadanes algoritm:
Här är stegen för Kadanes algoritm:
Steg 1) Skapa två variabler, current_sum och max_sum.
"Current_sum" kommer att behålla värdet på den maximala summan som slutar i ett specifikt arrayindex, medan "max_sum" kommer att lagra det maximala summeringsvärdet hittills.
Steg 2) Vi lägger till värdet med current_sum för varje matriselement. Sedan kontrollerar vi två villkor nedan:
- Om current_sum är mindre än det aktuella elementet kommer värdet för current_sum att vara det aktuella elementet.
- Om max_summa är mindre än aktuell_summa, kommer max_summa att vara aktuell_summa.
Steg 3) Genom att utföra det föregående steget för hela arrayen kommer vi att ha den största summan sammanhängande subarrayen i variabeln "max_sum".
Exempel på Kadanes algoritm
Vi kommer att demonstrera Kadaness algoritm med en liten array och diskutera varje steg för att hitta den största summan sammanhängande subarrayen.
Låt oss anta att den givna arrayen är som följande:
Här är stegen i Kadanes algoritm:
Steg 1) Skapa två variabler, current_sum och max_sum. Tilldela INT_MIN till max_summan och noll till den aktuella_summan. (Här betyder INT_MIN det lägsta heltal).
Steg 2) Vid index 0 är värdet 4. Så, strömsumman = 0 + 4 eller 4. Här är strömsumman större än maxsumman, maxsumman blir 4.
Steg 3) Vid index 1 är värdet -2. Så, den nuvarande_summan = 4 + (-2) eller 2.
Den här gången är den aktuella_summan mindre än max_summan. Som ett resultat kommer värdet för max_sum inte att uppdateras.
Steg 4) Nästa värde är 1. Om vi adderar detta med den aktuella_summan, blir den aktuella_summan 3. Ändå är max_summan större än den aktuella_summan. Så max_summan kommer inte att uppdateras.
Steg 5) Vid index 3 är värdet tre. Vi uppdaterar värdet genom att öka den aktuella_summan med 3. Så den aktuella_summan blir 6.
I det här fallet är max_summa mindre än nuvarande_summa. Så max_sum kommer att uppdateras med värdet på aktuell_summa.
Steg 6) För det sista elementet i arrayen har vi -1. Om vi adderar detta med aktuell_summa, blir aktuell_summa 5, vilket är mindre än max_summan. Så max_summan förblir 6.
När vi nådde slutet av arrayen slutar algoritmen här. Nu innehåller "max_sum" undermatrisen för maximal summa. Vilket är 5. Undermatrisen är {4,-2,1,3}.
Pseudokod för Kadanes algoritm
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++Implementering av Kadanes algoritm
#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]));
}
Produktion:
largest sum is 12
Python Implementering av Kadanes algoritm
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])
Produktion:
largest sum is 12
Komplexitetsanalys för största summa sammanhängande subarray
Det enkla tillvägagångssättet använder två slingor. Den metoden beräknar alla möjliga subarraysummor för att hitta den största. Det är en brute force-strategi. Varje slinga löper till slutet av array.
Om en array har totalt N element och sedan med två slingor går vi igenom N2 element. Som ett resultat blir tidskomplexiteten för ett enkelt tillvägagångssätt för att hitta den största summan sammanhängande subarrayen O(N2). Här betyder "O" komplexitetsfunktionen.
Å andra sidan är Kadanes algoritm den dynamiska programmeringsmetoden för att hitta den maximala sammanhängande summasubarrayen. Om du följer exemplet eller koden ser du att vi bara använder en slinga.
Som ett resultat, om inmatningsmatrisen har en storlek på N, då kommer tidskomplexiteten för Kadanes algoritm att vara O(N). Detta är snabbare än det enkla tillvägagångssättet. Till exempel en array som innehåller 100 element. Det enkla tillvägagångssättet kommer att ta 100*100 eller 10,000 100 CPU-tid. Men Kadane's Algorithm tar bara XNUMX CPU-tid.
