Kadence's algoritme: grootste som aaneengesloten subarray

Wat is de grootste som van aaneengesloten submatrices?

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.

Neem bijvoorbeeld de array {-10, 5, 1, 6, -9, 2, -7, 3, -5}. De submatrices hiervan kunnen {-10, 5, 1, 6}, {5, 1, 6} of {2, -7, 3, -5} zijn, enzovoort. {5, 1, 6, 3} kan echter geen submatrix zijn, omdat de elementen niet in een aaneengesloten reeks staan.

Zoals je ziet, heeft de gemarkeerde subreeks {5, 1, 6} de hoogste somwaarde van alle subreeksen:

De som van de subreeks {5, 1, 6} is 12, de maximale som van alle mogelijke subreeksen van de bovenstaande reeks. Dus voor deze reeks is de aaneengesloten subreeks met de maximale som {5, 1, 6}.

Eenvoudige aanpak voor het oplossen van de grootste som van aaneengesloten submatrices

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.

Hieronder staat het stroomdiagram voor de eenvoudige methode om de grootste aaneengesloten subreeks met de hoogste som te vinden. Dit is een brute-force-methode, waarbij we elke mogelijke subreeks doorlopen.

Hier zijn de eenvoudige stappen om dit te doen.

Stap 1) initialiseren max_sum met de minimale integerwaarde en set beginnen en einde tot nul.

Stap 2) Laat i en j array-indexen waar j is groter dan of gelijk aan i; i markeert het begin van de submatrix en j het einde ervan.

Stap 3) huidige_som houdt de lopende som bij. Controleer na elke update of huidige_som groter dan max_sum.

Stap 4) If huidige_som is groter, vervang max_sum mee.

Stap 5) . j Als het einde van de array is bereikt, verhoog dan de waarde. i en reset huidige_som om 0.

Stap 6) Herhaal tot i bereikt het einde van de array. max_sum dan bevat het de grootste som van de submatrices.

Pseudo Code voor een eenvoudige aanpak

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

C++ Implementatie van een 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 een 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 van een aaneengesloten subreeks te vinden

Het algoritme van Kadane is een dynamische programmeermethode die gebruikmaakt van één lus in plaats van twee. Het kan arrays verwerken met een mix van positieve en negatieve getallen, zolang er maar minstens één niet-negatieve waarde is.

We hebben slechts twee variabelen nodig om de grootste aaneengesloten subreeks met de hoogste som te vinden. Hier is het stroomdiagram:

Hier zijn de stappen voor het Kadane-algoritme:

Stap 1) Maak twee variabelen aan, huidige_som en max_sum.

huidige_som bewaart de maximale som die eindigt op een specifieke array-index, terwijl max_sum slaat de grootste tot nu toe waargenomen somwaarde op.

Stap 2) Voeg elk element van de array toe aan huidige_somControleer vervolgens de twee onderstaande voorwaarden:

• If huidige_som als het element kleiner is dan het huidige element, dan huidige_som wordt het huidige element.
• If max_sum is minder dan huidige_somdan max_sum wordt huidige_som.

Stap 3) Nadat de vorige stap voor de hele array is herhaald, max_sum bevat de grootste som van de aaneengesloten submatrices.

Voorbeeld van het algoritme van Kadane

We demonstreren Kadane's algoritme op een kleine array en doorlopen elke stap om de grootste aaneengesloten subarray met de grootste som te vinden.

Laten we aannemen dat de gegeven array er als volgt uitziet:

Hieronder volgen de stappen van Kadane's algoritme:

Stap 1) Maak twee variabelen aan, huidige_som en max_sumWijs INT_MIN toe aan max_sum en nul tot huidige_somHier staat INT_MIN voor de minimale integerwaarde.

Stap 2) Bij index 0 is de waarde 4. Dus, huidige_som = 0 + 4 = 4. Omdat huidige_som is groter dan max_sum, max_sum wordt 4.

Stap 3) Bij index 1 is de waarde -2. Dus, huidige_som = 4 + (-2) = 2.

Deze keer huidige_som is minder dan max_sumAls gevolg hiervan is de waarde van max_sum is niet bijgewerkt.

Stap 4) De volgende waarde is 1. Door deze toe te voegen aan huidige_som geeft 3. Omdat max_sum (4) is nog steeds groter dan huidige_som, max_sum is niet bijgewerkt.

Stap 5) Bij index 3 is de waarde 3. Oplopend huidige_som vermenigvuldigd met 3 geeft huidige_som = 6.

In dit geval, max_sum is kleiner dan huidige_som, dus max_sum wordt bijgewerkt met de waarde van huidige_som.

Stap 6) Voor het laatste element van de array hebben we -1. Als we dat optellen bij... huidige_som geeft 5, wat kleiner is dan max_sum. Zo, max_sum blijft 6.

Omdat we het einde van de array hebben bereikt, eindigt het algoritme hier. Nu, max_sum Bevat de maximale som, namelijk 6. De subreeks is {4, -2, 1, 3}.

Pseudo Code voor Kadane's 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++ 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 -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 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 van aaneengesloten subarrays

De eenvoudige aanpak gebruikt twee lussen om elke mogelijke som van de submatrices te berekenen en de grootste te vinden. Het is een brute-force-aanpak; elke lus wordt tot het einde van de matrix uitgevoerd. reeksgeven O(N²) tijd.

Het algoritme van Kadane gebruikt slechts één lus, wat resulteert in een tijdscomplexiteit van O(N) en een geheugenverbruik van O(1). Bij een array van 100 elementen voert de eenvoudige aanpak 100 × 100 = 10,000 bewerkingen uit, terwijl Kadane er slechts 100 uitvoert — een aanzienlijke snelheidsverbetering voor grote invoerwaarden.

Veelgestelde vragen