Kadence-Algorithmus: Größtes zusammenhängendes Subarray mit Summe

Was ist die größte Summe zusammenhängender Subarrays?

Ein Subarray ist ein kontinuierlicher Teil eines Arrays. Es kann ein einzelnes Element eines Arrays oder ein Teil des Arrays sein. Das zusammenhängende Subarray mit der größten Summe bedeutet ein Subarray mit dem maximalen Summenwert.

Ein Array ist beispielsweise {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Seine Unterarrays können sein: {-10,5,1,6} oder {5,1,6} oder {2,7,3, -5} usw. Aber {5,1,6,3} kann kein a sein Subarray, weil sie die Sequenzen nicht beibehalten.

Wenn Sie bemerken, dass unter allen Teilarrays das folgende hervorgehobene Teilarray (5,1,6) den maximalen Summenwert hat:

Die Summe des Subarrays {5,1,6} = 11 ist die maximale Summe in allen möglichen Kombinationen von Subarrays des obigen Arrays. Für das obige Array beträgt das maximale Unterarray also {5,1,6}.

Kadence-Algorithmus: Größtes zusammenhängendes Subarray mit Summe

Einfacher Ansatz zur Lösung des zusammenhängenden Subarrays mit der größten Summe

Der einfache Weg, dieses Problem zu lösen, besteht darin, zwei Schleifen zu verwenden, um alle Unterarrays zu finden, die Summe zu berechnen und dann ihren Maximalwert zu ermitteln.

Hier ist das Flussdiagramm für den einfachen Ansatz zum Finden des größten zusammenhängenden Teilarrays. Dies ist ein Brute-Force-Ansatz, da wir alle möglichen Unterarrays durchgehen.

Hier sind die einfachen Schritte, um dies zu tun.

Schritt 1) Initialisieren Sie max_sum mit dem minimalen ganzzahligen Wert und weisen Sie den Variablen „begin“ und „end“ den Wert Null zu.

Schritt 2) Seien i und j der Index des Arrays, wobei „j“ größer als gleich „i“ ist. Es stellt den Anfangsindex des Subarrays dar und „j“ stellt den Endindex des Subarrays dar.

Schritt 3) „Current_sum“ enthält die Summe des Subarrays. Überprüfen Sie nach der Berechnung der aktuellen Summe, ob current_sum größer als max_sum ist.

Schritt 4) Wenn current_sum größer ist, ersetzen Sie max_sum durch die aktuelle Summe.

Schritt 5) Überprüfen Sie, ob „j“ das Ende des Arrays erreicht oder nicht. Wenn „j“ das Ende des Arrays erreicht, erhöhen Sie „i“ und ändern Sie den Wert „current_sum“ auf 0.

Schritt 6) Führen Sie alle diese Schritte aus, bis „i“ das Ende des Arrays erreicht.

Schritt 7) Am Ende dieser beiden Schleifen enthält max_sum die größte Subarray-Summe.

Pseudocode für einfachen Ansatz

  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++ Implementierung des einfachen Ansatzes

#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]));
}

Ausgang:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Python Implementierung eines einfachen Ansatzes

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)

Ausgang:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Kadanes Algorithmus zum Finden des größten zusammenhängenden Subarrays

Kadanes Algorithmus ist eine Art Methode der „dynamischen Programmierung“. Hier verwenden wir eine Schleife anstelle von zwei Schleifen. Die allgemeine Implementierung des Kadane-Algorithmus funktioniert nur für Arrays positiver Zahlen.

Wir benötigen nur zwei Variablen, um das zusammenhängende Subarray mit der größten Summe zu finden. Hier ist das Flussdiagramm für Kadanes Algorithmus:

Hier sind die Schritte für Kadanes Algorithmus:

Schritt 1) Erstellen Sie zwei Variablen, current_sum und max_sum.

„Current_sum“ behält den Wert der maximalen Summe, die in einem bestimmten Array-Index endet, während „max_sum“ den bisherigen maximalen Summenwert speichert.

Schritt 2) Wir addieren den Wert mit der aktuellen_Summe für jedes Array-Element. Dann prüfen wir unten zwei Bedingungen:

• Wenn current_sum kleiner als das aktuelle Element ist, ist der current_sum-Wert das aktuelle Element.
• Wenn max_sum kleiner als current_sum ist, ist max_sum gleich current_sum.

Schritt 3) Wenn wir den vorherigen Schritt für das gesamte Array ausführen, erhalten wir die größte Summe zusammenhängender Unterarrays in der Variablen „max_sum“.

Beispiel für Kadanes Algorithmus

Wir demonstrieren den Kadanes-Algorithmus mit einem kleinen Array und diskutieren jeden Schritt zum Finden des größten zusammenhängenden Subarrays.

Nehmen wir an, das angegebene Array sieht wie folgt aus:

Hier sind die Schritte von Kadanes Algorithmus:

Schritt 1) Erstellen Sie zwei Variablen, current_sum und max_sum. Weisen Sie INT_MIN der max_sum und Null der current_sum zu. (Hier bedeutet INT_MIN die minimale Ganzzahl).

Schritt 2) Bei Index 0 ist der Wert 4. Also ist die aktuelle_Summe = 0 + 4 oder 4. Hier ist die aktuelle_Summe größer als die maximale_Summe, die maximale_Summe beträgt 4.

Schritt 3) Bei Index 1 beträgt der Wert -2. Also ist die aktuelle_Summe = 4 + (-2) oder 2.

Diesmal ist die aktuelle Summe kleiner als die maximale Summe. Infolgedessen wird der Wert von max_sum nicht aktualisiert.

Schritt 4) Der nächste Wert ist 1. Wenn wir dies mit der aktuellen_Summe addieren, beträgt die aktuelle_Summe 3. Dennoch ist die maximale_Summe größer als die aktuelle_Summe. Daher wird die max_sum nicht aktualisiert.

Schritt 5) Bei Index 3 beträgt der Wert drei. Wir aktualisieren den Wert, indem wir die aktuelle_Summe um 3 erhöhen. Die aktuelle_Summe beträgt also 6.

In diesem Fall ist die max_sum kleiner als die current_sum. Max_sum wird also mit dem Wert von current_sum aktualisiert.

Schritt 6) Für das letzte Element des Arrays haben wir -1. Wenn wir dies mit der aktuellen_Summe addieren, beträgt die aktuelle_Summe 5, was kleiner als die maximale_Summe ist. Die max_sum bleibt also 6.

Da wir das Ende des Arrays erreicht haben, endet der Algorithmus hier. Jetzt enthält „max_sum“ das Subarray mit der maximalen Summe. Das ist 5. Das Subarray ist {4,-2,1,3}.

Pseudocode für Kadanes Algorithmus

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++Implementierung des Kadane-Algorithmus

#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]));
}

Ausgang:

largest sum is 12

Python Implementierung des Kadane-Algorithmus

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])

Ausgang:

largest sum is 12

Komplexitätsanalyse für das größte zusammenhängende Teilarray

Der einfache Ansatz verwendet zwei Schleifen. Diese Methode berechnet alle möglichen Subarray-Summen, um die größte zu finden. Es ist ein Brute-Force-Ansatz. Jede Schleife läuft bis zum Ende Array.

Wenn ein Array insgesamt hat N Elemente, dann werden wir mit zwei Schleifen durch N gehen² Elemente. Als Ergebnis wird die Zeitkomplexität für einen einfachen Ansatz zum Finden des größten zusammenhängenden Teilarrays sein O(N2). Dabei steht „O“ für die Komplexitätsfunktion.

Andererseits ist der Kadane-Algorithmus die Methode der dynamischen Programmierung, um das maximale zusammenhängende Summen-Subarray zu finden. Wenn Sie dem Beispiel oder dem Code folgen, werden Sie feststellen, dass wir nur eine Schleife verwenden.

Dies führt dazu, dass das Eingabearray eine Größe von hat N, dann beträgt die Zeitkomplexität von Kadanes Algorithmus O(N). Dies ist schneller als der einfache Ansatz. Beispielsweise ein Array mit 100 Elementen. Der einfache Ansatz benötigt 100*100 oder 10,000 CPU-Zeit. Aber Kadanes Algorithmus benötigt nur 100 CPU-Zeit.