Kadence's Algorithm: Största summa sammanhängande subarray

Vilken är den största sammanhängande submatrisen?

En subarray är en kontinuerlig del av en array. Det kan vara ett enstaka element i en array eller en del av arrayen. Den största summan sammanhängande delmatrisen betyder en delmatris som har det maximala summavärdet.

Ta till exempel arrayen {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Dess underarrayer kan vara {-10, 5, 1, 6}, {5, 1, 6} eller {2, -7, 3, -5} och så vidare. Däremot kan {5, 1, 6, 3} inte vara en underarray eftersom elementen inte är i en sammanhängande sekvens.

Om du märker att bland alla delmatriser har den markerade delmatrisen {5, 1, 6} det maximala summeringsvärdet:

Summan av delmatrisen {5, 1, 6} är 12, den maximala summan över alla möjliga delmatriser i ovanstående matris. Så för denna matris är den maximala summan av den sammanhängande delmatrisen {5, 1, 6}.

Enkel metod för att lösa den största summan av sammanhängande delmatriser

Det enkla sättet att lösa detta problem är att använda två slingor för att hitta alla subarrayer, beräkna summan och sedan hitta dess maximala värde.

Här är flödesschemat för den enkla metoden för att hitta den största summan av en sammanhängande delmatris. Detta är en brute-force-metod, eftersom vi går igenom alla möjliga delmatriser.

Här är de enkla stegen för att göra detta.

Steg 1) initialisera max_sum med det minsta heltalsvärdet och uppsättningen börja och änden till noll.

Steg 2) Låt i och j vara arrayindex där j är större än eller lika med i; i markerar subarrayens start och j dess slut.

Steg 3) aktuell_summa håller den löpande summan. Kontrollera efter varje uppdatering om aktuell_summa är större än max_sum.

Steg 4) If aktuell_summa är större, ersätt max_sum med det.

Steg 5) När j når slutet av arrayen, öka i och återställ aktuell_summa till 0.

Steg 6) Upprepa tills i når slutet av arrayen. max_sum innehar sedan den största delmatrissumman.

Pseudo Code för enkel metod

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        store the maximum subArray
    return the maximum sum

C++ Implementering av 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]));
}

Produktion:

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

Python Implementering av Simple Approach

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)

Produktion:

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

Kadanes algoritm för att hitta den största summan av sammanhängande delmatris

Kadanes algoritm är en dynamisk programmeringsmetod som använder en enda loop istället för två. Den hanterar arrayer med blandade positiva och negativa tal, så länge minst ett värde inte är negativt.

Vi behöver bara två variabler för att hitta den största summan av den sammanhängande delmatrisen. Här är flödesschemat:

Här är stegen för Kadanes algoritm:

Steg 1) Skapa två variabler, aktuell_summa och max_sum.

aktuell_summa behåller den maximala summan som slutar vid ett specifikt arrayindex, medan max_sum lagrar det största summeringsvärdet som hittills observerats.

Steg 2) Lägg till varje arrayelement till aktuell_summaKontrollera sedan de två villkoren nedan:

• If aktuell_summa är mindre än det aktuella elementet, då aktuell_summa blir det aktuella elementet.
• If max_sum är mindre än aktuell_summaoch sedan max_sum blir aktuell_summa.

Steg 3) Efter att ha upprepat föregående steg för hela arrayen, max_sum innehar den största summan av den sammanhängande delmatrisen.

Exempel på Kadanes algoritm

Vi demonstrerar Kadanes algoritm på en liten array och går igenom varje steg för att hitta den största summan av den sammanhängande subarrayen.

Låt oss anta att den givna arrayen är som följande:

Här är stegen i Kadanes algoritm:

Steg 1) Skapa två variabler, aktuell_summa och max_sumTilldela INT_MIN till max_sum och noll till aktuell_summaHär representerar INT_MIN det minsta heltalsvärdet.

Steg 2) Vid index 0 är värdet 4. Så, aktuell_summa = 0 + 4 = 4. Eftersom aktuell_summa är större än max_sum, max_sum blir 4.

Steg 3) Vid index 1 är värdet -2. Så, aktuell_summa = 4 + (-2) = 2.

Den här gången aktuell_summa är mindre än max_sumSom ett resultat av detta minskar värdet av max_sum uppdateras inte.

Steg 4) Nästa värde är 1. Lägger man till det aktuell_summa ger 3. Eftersom max_sum (4) är fortfarande större än aktuell_summa, max_sum uppdateras inte.

Steg 5) Vid index 3 är värdet 3. Ökning aktuell_summa med 3 ger aktuell_summa = 6.

I det här fallet, max_sum är mindre än aktuell_summa, Så max_sum uppdateras med värdet av aktuell_summa.

Steg 6) För det sista elementet i arrayen har vi -1. Vi lägger till det aktuell_summa ger 5, vilket är mindre än max_sum. Så, max_sum återstår 6 XNUMX XNUMX.

När vi nått slutet av arrayen slutar algoritmen här. Nu, max_sum innehåller den maximala summan, som är 6. Delmatrisen är {4, -2, 1, 3}.

Pseudo Code för Kadanes algoritm

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++ Implementering av Kadanes algoritm

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

Produktion:

largest sum is 12

Python Implementering av Kadanes algoritm

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

Produktion:

largest sum is 12

Komplexitetsanalys för största summa sammanhängande subarray

Den enkla metoden använder två loopar för att beräkna varje möjlig subarraysumma och hitta den största. Det är en brute-force-metod; varje loop går till slutet av array, ger O(N²) tid.

Kadanes algoritm använder bara en loop, vilket ger O(N) tid och O(1) extra utrymme. På en array med 100 element utför den enkla metoden 100 × 100 = 10 000 operationer, medan Kadanes algoritm bara utför 100 – en dramatisk ökning av hastigheten för stora indata.

Vanliga frågor