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

Was ist die größte zusammenhängende Teilmatrix?

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.

Betrachten wir beispielsweise das Array {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Seine Teilarrays können beispielsweise {-10, 5, 1, 6}, {5, 1, 6} oder {2, -7, 3, -5} sein. Allerdings kann {5, 1, 6, 3} kein Teilarray sein, da die Elemente nicht zusammenhängend angeordnet sind.

Wie Sie sehen, hat unter allen Teilarrays das hervorgehobene Teilarray {5, 1, 6} den höchsten Summenwert:

Die Summe des Teilarrays {5, 1, 6} beträgt 12, die maximale Summe aller möglichen Teilarrays des obigen Arrays. Daher ist für dieses Array das Teilarray mit der größten Summe {5, 1, 6}.

Einfacher Ansatz zur Lösung des Problems der größten Summe in zusammenhängenden Teilarrays

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 zur Ermittlung des größten zusammenhängenden Teilarrays mit der größten Summe. Es handelt sich um einen Brute-Force-Ansatz, da wir jedes mögliche Teilarray durchgehen.

Hier sind die einfachen Schritte, um dies zu tun.

Schritt 1) Initialisieren max_sum mit dem kleinsten ganzzahligen Wert und setzen beginnen und Ende bis Null.

Schritt 2) Lassen i und j seien Array-Indizes, wobei j ist größer oder gleich i; i markiert den Beginn des Teilarrays und j sein Ende.

Schritt 3) aktuelle_summe enthält die laufende Summe. Nach jeder Aktualisierung prüfen, ob aktuelle_summe größer ist als max_sum.

Schritt 4) If aktuelle_summe ist größer, ersetzen max_sum mit ihm.

Schritt 5) Wenn die Funktion j Erreicht das Ende des Arrays, inkrementiere i und zurücksetzen aktuelle_summe um 0.

Schritt 6) Wiederhole bis i erreicht das Ende des Arrays. max_sum enthält dann die größte Teilarray-Summe.

Spitzname Code für den einfachen Ansatz

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        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 des 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 zur Bestimmung der größten zusammenhängenden Teilmatrix

Kadanes Algorithmus ist eine Methode der dynamischen Programmierung, die anstelle von zwei Schleifen nur eine einzige verwendet. Er verarbeitet Arrays mit gemischten positiven und negativen Zahlen, solange mindestens ein Wert nicht negativ ist.

Wir benötigen nur zwei Variablen, um das zusammenhängende Teilarray mit der größten Summe zu finden. Hier ist das Flussdiagramm:

Hier sind die Schritte für Kadanes Algorithmus:

Schritt 1) Erstelle zwei Variablen, aktuelle_summe und max_sum.

aktuelle_summe behält die maximale Summe bei, die an einem bestimmten Array-Index endet, während max_sum speichert den bisher größten beobachteten Summenwert.

Schritt 2) Füge jedes Array-Element hinzu zu aktuelle_summeÜberprüfen Sie anschließend die beiden folgenden Bedingungen:

• If aktuelle_summe ist kleiner als das aktuelle Element, dann aktuelle_summe wird zum aktuellen Element.
• If max_sum weniger als aktuelle_summe und dann max_sum wird aktuelle_summe.

Schritt 3) Nachdem der vorherige Schritt für das gesamte Array wiederholt wurde, max_sum enthält die größte zusammenhängende Teilmatrix.

Beispiel für Kadanes Algorithmus

Wir demonstrieren Kadanes Algorithmus an einem kleinen Array und gehen jeden Schritt der Suche nach dem größten zusammenhängenden Teilarray durch.

Nehmen wir an, das gegebene Array sieht folgendermaßen aus:

Hier sind die Schritte des Kadane-Algorithmus:

Schritt 1) Erstelle zwei Variablen, aktuelle_summe und max_sumWeisen Sie INT_MIN zu max_sum und Null bis aktuelle_summeHierbei stellt INT_MIN den kleinsten ganzzahligen Wert dar.

Schritt 2) Bei Index 0 beträgt der Wert 4. Also, aktuelle_summe = 0 + 4 = 4. Da aktuelle_summe ist größer als max_sum, max_sum wird 4.

Schritt 3) An Index 1 beträgt der Wert -2. aktuelle_summe = 4 + (-2) = 2.

Diesmal aktuelle_summe weniger als max_sumFolglich ist der Wert von max_sum wird nicht aktualisiert.

Schritt 4) Der nächste Wert ist 1. Addiert man ihn zu aktuelle_summe ergibt 3. Da max_sum (4) ist immer noch größer als aktuelle_summe, max_sum wird nicht aktualisiert.

Schritt 5) An Index 3 ist der Wert 3. Inkrementierung aktuelle_summe durch 3 ergibt aktuelle_summe = 6.

In diesem Fall steht: max_sum ist kleiner als aktuelle_summe, damit max_sum wird mit dem Wert von aktualisiert aktuelle_summe.

Schritt 6) Das letzte Element des Arrays ist -1. Wir addieren es zu aktuelle_summe ergibt 5, was kleiner ist als max_sum. So, max_sum bleibt 6.

Da wir das Ende des Arrays erreicht haben, endet der Algorithmus hier. Nun max_sum enthält die maximale Summe, die 6 beträgt. Das Teilarray ist {4, -2, 1, 3}.

Spitzname Code für Kadanes Algorithmus

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element 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 -1,000,000,000
    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, um jede mögliche Teilarray-Summe zu berechnen und die größte zu finden. Es handelt sich um einen Brute-Force-Ansatz; jede Schleife wird bis zum Ende des Arrays durchlaufen. Arraygeben O(N²) Zeit.

Kadanes Algorithmus benötigt nur eine Schleife, was zu einer Laufzeit von O(N) und einem zusätzlichen Speicherbedarf von O(1) führt. Bei einem Array mit 100 Elementen führt der einfache Ansatz 100 × 100 = 10,000 Operationen aus, während Kadanes Algorithmus nur 100 Operationen benötigt – eine enorme Beschleunigung bei großen Eingaben.

Häufig gestellte Fragen