Kadences algoritme: Største sum sammenhængende subarray

Hvad er den største sum sammenhængende undergruppe?

Et underarray er en kontinuerlig del af et array. Det kan være et enkelt element i et array eller en brøkdel af arrayet. Den største sum sammenhængende subarray betyder en subarray, der har den maksimale sumværdi.

Tag for eksempel arrayet {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Dets underarrays kan være {-10, 5, 1, 6}, {5, 1, 6} eller {2, -7, 3, -5} osv. {5, 1, 6, 3} kan dog ikke være et underarray, fordi elementerne ikke er i en sammenhængende rækkefølge.

Hvis du bemærker, at blandt alle underarraysene har det fremhævede underarray {5, 1, 6} den maksimale summationsværdi:

Summen af ​​underarrayet {5, 1, 6} er 12, den maksimale sum på tværs af alle mulige underarrayer i ovenstående array. Så for dette array er den maksimale sum af sammenhængende underarrayer {5, 1, 6}.

Simpel tilgang til løsning af den største sum af sammenhængende underarray

Den enkle måde at løse dette problem på er at bruge to sløjfer til at finde alle subarrays, beregne summen og derefter finde dens maksimale værdi.

Her er flowdiagrammet for den simple metode til at finde det største summen af ​​sammenhængende underarray. Dette er en brute-force-metode, da vi gennemgår alle mulige underarrayer.

Her er de enkle trin til at gøre dette.

Trin 1) Initialiser maks_sum med den minimale heltalsværdi og sæt begynde og ende til nul.

Trin 2) Lade i og j være arrayindekser hvor j er større end eller lig med i; i markerer starten af ​​underarrayet og j dens ende.

Trin 3) nuværende_sum indeholder den løbende sum. Efter hver opdatering skal du kontrollere, om nuværende_sum er større end maks_sum.

Trin 4) If nuværende_sum er større, erstat maks_sum med det.

Trin 5) Når j når slutningen af ​​arrayet, forøg i og nulstil nuværende_sum til 0.

Trin 6) Gentag indtil i når slutningen af ​​arrayet. maks_sum indeholder så den største underarraysum.

Kaldenavn Code for simpel tilgang

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

Output:

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

Python Implementering af 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)

Output:

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

Kadanes algoritme til at finde den største sum af sammenhængende undergruppe

Kadanes algoritme er en dynamisk programmeringsmetode, der bruger et enkelt loop i stedet for to. Den håndterer arrays med blandede positive og negative tal, så længe mindst én værdi ikke er negativ.

Vi behøver kun to variabler for at finde den største sum af sammenhængende underarray. Her er flowdiagrammet:

Her er trinene til Kadanes algoritme:

Trin 1) Opret to variabler, nuværende_sum og maks_sum.

nuværende_sum bevarer den maksimale sum, der ender ved et specifikt arrayindeks, mens maks_sum gemmer den største summeringsværdi, der er observeret hidtil.

Trin 2) Tilføj hvert array-element til nuværende_sumTjek derefter de to betingelser nedenfor:

• If nuværende_sum er mindre end det aktuelle element, så nuværende_sum bliver det aktuelle element.
• If maks_sum er mindre end nuværende_sum, derefter maks_sum bliver nuværende_sum.

Trin 3) Efter at have gentaget det foregående trin for hele arrayet, maks_sum indeholder den største sum af sammenhængende underarray.

Eksempel på Kadanes algoritme

Vi demonstrerer Kadanes algoritme på et lille array og gennemgår hvert trin i at finde det største summen af ​​et sammenhængende underarray.

Lad os antage, at det givne array er som følger:

Her er trinnene i Kadanes algoritme:

Trin 1) Opret to variabler, nuværende_sum og maks_sumTildel INT_MIN til maks_sum og nul til nuværende_sumHer repræsenterer INT_MIN den minimale heltalsværdi.

Trin 2) Ved indeks 0 er værdien 4. Så, nuværende_sum = 0 + 4 = 4. Da nuværende_sum er større end maks_sum, maks_sum bliver 4.

Trin 3) Ved indeks 1 er værdien -2. Så, nuværende_sum = 4 + (-2) = 2.

Denne gang nuværende_sum er mindre end maks_sumSom følge heraf er værdien af maks_sum er ikke opdateret.

Trin 4) Den næste værdi er 1. Lægger man den til nuværende_sum giver 3. Siden maks_sum (4) er stadig større end nuværende_sum, maks_sum er ikke opdateret.

Trin 5) Ved indeks 3 er værdien 3. Inkrementering nuværende_sum med 3 giver nuværende_sum = 6.

I dette tilfælde, maks_sum er mindre end nuværende_sum, Så maks_sum opdateres med værdien af nuværende_sum.

Trin 6) For det sidste element i arrayet har vi -1. Lægger vi det til nuværende_sum giver 5, hvilket er mindre end maks_sum. Så, maks_sum forbliver 6.

Da vi nåede slutningen af ​​arrayet, slutter algoritmen her. Nu, maks_sum indeholder den maksimale sum, som er 6. Underarrayet er {4, -2, 1, 3}.

Kaldenavn Code for Kadanes algoritme

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 af Kadanes Algoritme

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

Output:

largest sum is 12

Python Implementering af Kadanes Algoritme

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

Kompleksitetsanalyse for Største Sum Sammenhængende Subarray

Den simple tilgang bruger to løkker til at beregne alle mulige subarray-summer og finde den største. Det er en brute-force-tilgang; hver løkke løber til slutningen af matrix, giver O(N²) tid.

Kadanes algoritme bruger kun én løkke, hvilket giver O(N) tid og O(1) ekstra plads. På et array af 100 elementer udfører den simple tilgang 100 × 100 = 10,000 operationer, mens Kadanes kun udfører 100 - en dramatisk hastighedsforøgelse for store input.

Ofte Stillede Spørgsmål