Kadence's algoritme: grootste som aaneengesloten subarray
Sara Chen
Wat is de grootste som aaneengesloten subarray?
Een subarray is een doorlopend onderdeel van een array. Het kan een enkel element van een array zijn of een deel van de array. De grootste som aaneengesloten subarray betekent een subarray die de maximale somwaarde heeft.
Een array is bijvoorbeeld {-10, 5, 1, 6, -9, 2, -7, 3, -5}. De subarrays kunnen zijn: {-10,5,1,6} of {5,1,6} of {2,7,3, -5} enz. Maar {5,1,6,3} kan geen subarray omdat ze de reeksen niet onderhouden.
Als u opmerkt, heeft van alle subarrays de volgende gemarkeerde subarray (5,1,6) de hoogste sommatiewaarde:
De som van de subarray {5,1,6} = 11, is de maximale som in alle mogelijke combinaties van subarrays van de bovenstaande array. Voor de bovenstaande array is de maximale subarray dus {5,1,6}.
Kadence's algoritme: grootste som aaneengesloten subarray
Eenvoudige benadering voor het oplossen van de grootste som aaneengesloten subarray
De eenvoudige manier om dit probleem op te lossen is door twee lussen te gebruiken om alle subarrays te vinden, de som te berekenen en vervolgens de maximale waarde ervan te vinden.
Hier is het stroomdiagram voor de eenvoudige aanpak voor het vinden van de grootste som aaneengesloten subarray. Dit is een brute force-aanpak, omdat we alle mogelijke subarrays doorlopen.
Hier zijn de eenvoudige stappen om dit te doen.
Stap 1) Initialiseer de max_sum met een minimale gehele waarde en wijs variabelen “begin” en “end” toe met nul.
Stap 2) Laat i en j de index van de array zijn, waarbij “j” groter is dan gelijk aan “i”. Het vertegenwoordigt de beginindex van de subarray, en “j” vertegenwoordigt de eindindex van de subarray.
Stap 3) “Current_sum” bevat de som van de subarray. Controleer na het berekenen van de huidige som of current_sum groter is dan de max_sum.
Stap 4) Als current_sum groter is, vervang dan de max_sum door de huidige som.
Stap 5) Controleer of “j” het einde van de array bereikt of niet. Als “j” het einde van de array bereikt, verhoog dan “i” en verander de current_sum-waarde in 0.
Stap 6) Voer al deze stappen uit, totdat “i” het einde van de array bereikt.
Stap 7) Aan het einde van deze twee lussen bevat The max_sum de grootste subarraysom.
Pseudocode voor eenvoudige aanpak
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++ Implementatie van een eenvoudige aanpak
#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 Implementatie van een eenvoudige aanpak
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
Kadane's algoritme om de grootste som aaneengesloten subarray te vinden
Het algoritme van Kadane is een soort “Dynamisch Programmeren”-methode. Hier gebruiken we één lus in plaats van twee lussen. De algemene implementatie van het Kadane-algoritme werkt alleen voor arrays met positieve getallen.
We hebben slechts twee variabelen nodig om de grootste som aaneengesloten subarray te vinden. Hier is het stroomdiagram voor Kadane's algoritme:
Hier zijn de stappen voor het Kadane-algoritme:
Stap 1) Maak twee variabelen, current_sum en max_sum.
“Current_sum” behoudt de waarde van de maximale som die eindigt in een specifieke array-index, terwijl “max_sum” de maximale somwaarde tot nu toe opslaat.
Stap 2) We zullen de waarde optellen met de current_sum voor elk array-element. Vervolgens controleren we hieronder twee voorwaarden:
- Als current_sum kleiner is dan het huidige element, dan zal de current_sum-waarde het huidige element zijn.
- Als max_sum kleiner is dan current_sum, dan zal max_sum current_sum zijn.
Stap 3) Als we de vorige stap voor de hele array uitvoeren, hebben we de grootste som aaneengesloten subarray in de variabele "max_sum".
Voorbeeld van het algoritme van Kadane
We demonstreren het algoritme van Kadanes met een kleine array en bespreken elke stap van het vinden van de grootste som aaneengesloten subarray.
Laten we aannemen dat de gegeven array er als volgt uitziet:
Hier zijn de stappen van Kadane's algoritme:
Stap 1) Maak twee variabelen, current_sum en max_sum. Wijs INT_MIN toe aan de max_sum en nul aan de current_sum. (Hier betekent INT_MIN het minimale gehele getal).
Stap 2) Bij index 0 is de waarde 4. Dus de current_sum = 0 + 4 of 4. Hier is current_sum groter dan de max_sum, de max_sum is 4.
Stap 3) Bij index 1 is de waarde -2. Dus de huidige_som = 4 + (-2) of 2.
Deze keer is de huidige_som kleiner dan de max_som. Als gevolg hiervan wordt de waarde van max_sum niet bijgewerkt.
Stap 4) De volgende waarde is 1. Als we dit optellen bij de current_sum, dan wordt de current_sum 3. Toch is de max_sum groter dan de current_sum. De max_sum wordt dus niet bijgewerkt.
Stap 5) Bij index 3 is de waarde drie. We werken de waarde bij door de current_sum met 3 te verhogen. De current_sum wordt dus 6.
In dit geval is de max_sum kleiner dan de current_sum. Max_sum wordt dus bijgewerkt met de waarde current_sum.
Stap 6) Voor het laatste element van de array hebben we -1. Als we dit optellen bij de current_sum, wordt de current_sum 5, wat kleiner is dan de max_sum. De max_sum blijft dus 6.
Toen we het einde van de array bereikten, eindigt het algoritme hier. Nu bevat “max_sum” de maximale som-subarray. Dat is 5. De subarray is {4,-2,1,3}.
Pseudocode voor het algoritme van 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++Implementatie van het algoritme van 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]));
}
Output:
largest sum is 12
Python Implementatie van het algoritme van 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])
Output:
largest sum is 12
Complexiteitsanalyse voor de grootste som van aaneengesloten subarrays
De eenvoudige aanpak maakt gebruik van twee lussen. Die methode berekent alle mogelijke subarraysommen om de grootste te vinden. Het is een brute force-aanpak. Elke lus loopt tot het einde van de reeks.
Als een array in totaal N elementen, en vervolgens met behulp van twee lussen gaan we door N2 elementen. Als gevolg hiervan zal de tijdcomplexiteit voor een eenvoudige benadering om de grootste som aaneengesloten subarray te vinden, O(N2). Hierbij staat “O” voor de complexiteitsfunctie.
Aan de andere kant is het algoritme van Kadane de dynamische programmeermethode om de maximale aaneengesloten som-subarray te vinden. Als je het voorbeeld of de code volgt, zul je zien dat we slechts één lus gebruiken.
Als gevolg hiervan, als de invoerarray een grootte heeft van N, dan zal de tijdcomplexiteit van Kadane's algoritme O(N) zijn. Dit is sneller dan de eenvoudige benadering. Bijvoorbeeld, een array met 100 elementen. De eenvoudige benadering zal 100*100 of 10,000 CPU-tijd in beslag nemen. Maar het Kadane's algoritme zal slechts 100 CPU-tijd in beslag nemen.
