Kadences algoritme: Største sum sammenhængende subarray
Sarah Chen
Hvad er den største sum sammenhængende subarray?
Et underarray er en kontinuerlig del af et array. Det kan være et enkelt element i et array eller en brøkdel af arrayet. Den største sum sammenhængende subarray betyder en subarray, der har den maksimale sumværdi.
For eksempel er en matrix {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Dens underarrays kan være: {-10,5,1,6} eller {5,1,6} eller {2,7,3, -5} osv. Men {5,1,6,3} kan ikke være en subarray, fordi de ikke vedligeholder sekvenserne.
Hvis du bemærker, blandt alle subarrays, har følgende fremhævede subarray (5,1,6) den maksimale summeringsværdi:
Summen af underarrayet {5,1,6} = 11, er den maksimale sum i alle mulige kombinationer af underarray af ovenstående array. Så for ovenstående array er den maksimale underarray {5,1,6}.
Kadences algoritme: Største sum sammenhængende subarray
Enkel tilgang til at løse den største sum sammenhængende subarray
Den enkle måde at løse dette problem på er at bruge to sløjfer til at finde alle subarrays, beregne summen og derefter finde dens maksimale værdi.
Her er rutediagrammet for den enkle tilgang til at finde den største sum sammenhængende sub-array. Dette er en brute force tilgang, da vi gennemgår alle mulige subarrays.
Her er de enkle trin til at gøre dette.
Trin 1) Initialiser max_sum med mindste heltalsværdi og tildel variablerne "begynd" og "slut" med nul.
Trin 2) Lad i og j være indekset for arrayet, hvor "j" er større end lig med "i". Det repræsenterer underarrayets begyndelsesindeks, og "j" repræsenterer underarrayets slutindeks.
Trin 3) "Current_sum" vil indeholde summen af underarrayet. Efter at have beregnet den aktuelle sum, skal du kontrollere, om current_sum er større end max_sum.
Trin 4) Hvis aktuel_sum er større, skal du erstatte max_sum med den aktuelle sum.
Trin 5) Tjek, om "j" når slutningen af arrayet eller ej. Hvis "j" når slutningen af arrayet, skal du øge "i" og ændre den aktuelle_sum værdi til 0.
Trin 6) Udfør alle disse trin, indtil "i" når slutningen af arrayet.
Trin 7) I slutningen af disse to sløjfer vil max_sum indeholde den største subarray sum.
Pseudokode for enkel tilgang
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 af 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]));
}
Output:
largest sum is 12 largest sum contiguous subarray: 5 1 6
Python Implementering af enkel tilgang
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)
Output:
largest sum is 12 largest sum contiguous subarray: 5 1 6
Kadanes algoritme til at finde den største sum sammenhængende subarray
Kadanes Algoritme er en slags "Dynamisk Programmering" metode. Her bruger vi en løkke i stedet for to løkker. Generel implementering af Kadanes algoritme virker kun for positive tal-arrays.
Vi behøver kun to variable for at finde den største sum sammenhængende subarray. Her er flowdiagrammet for Kadanes algoritme:
Her er trinene til Kadanes algoritme:
Trin 1) Opret to variabler, current_sum og max_sum.
"Current_sum" vil beholde værdien af den maksimale sum, der ender i et specifikt array-indeks, mens "max_sum" vil gemme den maksimale summeringsværdi indtil videre.
Trin 2) Vi tilføjer værdien med den aktuelle_sum for hvert array-element. Så tjekker vi to betingelser nedenfor:
- Hvis aktuel_sum er mindre end det aktuelle element, vil aktuel_sum værdien være det aktuelle element.
- Hvis max_sum er mindre end aktuel_sum, så vil max_sum være aktuel_sum.
Trin 3) Når vi udfører det foregående trin for hele arrayet, vil vi have den største sum sammenhængende subarray i variablen "max_sum".
Eksempel på Kadanes algoritme
Vi demonstrerer Kadanes' algoritme med et lille array og diskuterer hvert trin for at finde den største sum sammenhængende underarray.
Lad os antage, at det givne array er som følgende:
Her er trinene i Kadanes algoritme:
Trin 1) Opret to variabler, current_sum og max_sum. Tildel INT_MIN til max_sum og nul til current_sum. (Her betyder INT_MIN det mindste heltal).
Trin 2) Ved indeks 0 er værdien 4. Så den aktuelle_sum = 0 + 4 eller 4. Her er strøm_sum større end maks_sum, vil maks_sum være 4.
Trin 3) Ved indeks 1 er værdien -2. Så den aktuelle_sum = 4 + (-2) eller 2.
Denne gang er den aktuelle_sum mindre end max_sum. Som følge heraf vil værdien af max_sum ikke blive opdateret.
Trin 4) Den næste værdi er 1. Hvis vi tilføjer dette med den aktuelle_sum, vil den aktuelle_sum være 3. Alligevel er max_sum større end den nuværende_sum. Så max_sum vil ikke blive opdateret.
Trin 5) Ved indeks 3 er værdien tre. Vi opdaterer værdien ved at øge den aktuelle_sum med 3. Så den nuværende_sum vil være 6.
I dette tilfælde er max_sum mindre end den aktuelle_sum. Så max_sum vil blive opdateret med værdien af current_sum.
Trin 6) For det sidste element i arrayet har vi -1. Hvis vi tilføjer dette med den aktuelle_sum, vil den nuværende_sum være 5, hvilket er mindre end max_sum. Så max_sum forbliver 6.
Da vi nåede slutningen af arrayet, slutter algoritmen her. Nu, "max_sum" indeholder den maksimale sum subarray. Hvilket er 5. Underarrayet er {4,-2,1,3}.
Pseudokode for Kadanes algoritme
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 af Kadanes Algoritme
#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]));
}
Output:
largest sum is 12
Python Implementering af Kadanes Algoritme
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])
Output:
largest sum is 12
Kompleksitetsanalyse for Største Sum Sammenhængende Subarray
Den enkle tilgang bruger to sløjfer. Denne metode beregner alle mulige subarray-summer for at finde den største. Det er en brute force tilgang. Hver sløjfe løber indtil slutningen af matrix.
Hvis et array har i alt N elementer, og ved hjælp af to sløjfer går vi gennem N2 elementer. Som et resultat vil tidskompleksiteten for en simpel tilgang til at finde den største sum sammenhængende subarray være O(N2). Her betyder "O" kompleksitetsfunktionen.
På den anden side er Kadanes algoritme den dynamiske programmeringsmetode til at finde den maksimale sammenhængende sum-subarray. Hvis du følger eksemplet eller koden, vil du se, at vi kun bruger én løkke.
Som et resultat, hvis input-arrayet har en størrelse på N, så vil tidskompleksiteten af Kadanes Algoritme være O(N). Dette er hurtigere end den simple tilgang. For eksempel et array, der indeholder 100 elementer. Den enkle tilgang vil tage 100*100 eller 10,000 CPU-tid. Men Kadane's Algoritme vil kun tage 100 CPU-tid.
