Kadence's algoritme: grootste som aaneengesloten subarray

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.

Grootste aaneengesloten subreeks

Als je tussen alle subarrays merkt dat following gemarkeerde subarray (5,1,6) heeft de maximale sommatiewaarde:

Grootste aaneengesloten subreeks

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.

Eenvoudige aanpak voor het oplossen van de grootste som

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 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 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:

Kadane's algoritme om het grootste bedrag te vinden

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 lijkt op de volgendewing:

Voorbeeld van het algoritme van Kadane

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.

Voorbeeld van het algoritme van Kadane

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.

Voorbeeld van het algoritme van Kadane

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.

Voorbeeld van het algoritme van Kadane

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.

Voorbeeld van het algoritme van Kadane

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.

Voorbeeld van het algoritme van Kadane

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 aaneengesloten subarray

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 is de tijd complexDit zal een eenvoudige benadering zijn om de grootste som aaneengesloten subarray te vinden O(N2). Hier betekent “O” de complexity-functie.

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 is de tijd complexDe kwaliteit van Kadane's algoritme zal O(N) zijn. Dit is sneller dan de eenvoudige aanpak. Bijvoorbeeld een array met 100 elementen. De eenvoudige aanpak kost 100*100 of 10,000 CPU-tijd. Maar het algoritme van Kadane kost slechts 100 CPU-tijd.