Kadenceův algoritmus: Souvislé dílčí pole s největším součtem

Jaký je největší součet souvislých podpolí?

Podpole je souvislá část pole. Může to být jeden prvek pole nebo nějaká část pole. Souvislé podpole s největším součtem znamená podpole, které má maximální hodnotu součtu.

Vezměte si například pole {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Jeho podpole mohou být {-10, 5, 1, 6}, {5, 1, 6} nebo {2, -7, 3, -5} atd. Nicméně {5, 1, 6, 3} nemůže být podpole, protože prvky nejsou v souvislé posloupnosti.

Pokud si všimnete, mezi všemi podpolemi má zvýrazněné podpole {5, 1, 6} maximální hodnotu součtu:

Součet podpole {5, 1, 6} je 12, což je maximální součet napříč všemi možnými podpolemi výše uvedeného pole. Takže pro toto pole je maximální součet souvislého podpole {5, 1, 6}.

Jednoduchý přístup k řešení největšího součtu souvislých podpolí

Jednoduchý způsob, jak tento problém vyřešit, je použít dvě smyčky k nalezení všech podpolí, vypočítat součet a pak najít jeho maximální hodnotu.

Zde je vývojový diagram jednoduchého přístupu k nalezení největšího součtu souvislých podpolí. Jedná se o přístup hrubé síly, protože procházíme všechna možná podpole.

Zde jsou jednoduché kroky, jak toho dosáhnout.

Krok 1) zahájit maximální_součet s minimální celočíselnou hodnotou a nastavenou začít a konec na nulu.

Krok 2) Nechat i a j být indexy pole, kde j je větší nebo rovno i; i označuje začátek podpole a j jeho konec.

Krok 3) aktuální_součet obsahuje průběžný součet. Po každé aktualizaci zkontrolujte, zda aktuální_součet je větší než maximální_součet.

Krok 4) If aktuální_součet je větší, nahraďte maximální_součet s ním.

Krok 5) Kdy j dosáhne konce pole, inkrementuje i a resetovat aktuální_součet na 0.

Krok 6) Opakujte, dokud i dosáhne konce pole. maximální_součet pak obsahuje největší součet podpolí.

Nepravý Code pro jednoduchý přístup

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

C++ Implementace jednoduchého přístupu

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

Výstup:

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

Python Implementace jednoduchého přístupu

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)

Výstup:

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

Kadaneův algoritmus pro nalezení největšího součtu souvislých podpolí

Kadaneův algoritmus je metoda dynamického programování, která používá jednu smyčku místo dvou. Zpracovává pole se smíšenými kladnými a zápornými čísly, pokud alespoň jedna hodnota je nezáporná.

K nalezení největšího součtu souvislého podpole potřebujeme pouze dvě proměnné. Zde je vývojový diagram:

Zde jsou kroky pro Kadaneův algoritmus:

Krok 1) Vytvořte dvě proměnné, aktuální_součet a maximální_součet.

aktuální_součet zachovává maximální součet, který končí na specifickém indexu pole, zatímco maximální_součet uchovává největší dosud pozorovanou součtovou hodnotu.

Krok 2) Přidat každý prvek pole do aktuální_součetPak zkontrolujte dvě níže uvedené podmínky:

• If aktuální_součet je menší než aktuální prvek, pak aktuální_součet stává se aktuálním prvkem.
• If maximální_součet je méně než aktuální_součet, pak maximální_součet se stává aktuální_součet.

Krok 3) Po zopakování předchozího kroku pro celé pole, maximální_součet obsahuje největší součet souvislých podpolí.

Příklad Kadaneova algoritmu

Kadaneův algoritmus demonstrujeme na malém poli a projdeme si každý krok hledání souvislého podpole s největším součtem.

Předpokládejme, že dané pole má následující tvar:

Zde jsou kroky Kadaneho algoritmu:

Krok 1) Vytvořte dvě proměnné, aktuální_součet a maximální_součetPřiřaďte INT_MIN k maximální_součet a nula až aktuální_součetZde INT_MIN představuje minimální celočíselnou hodnotu.

Krok 2) Na indexu 0 je hodnota 4. Takže, aktuální_součet = 0 + 4 = 4. Protože aktuální_součet je větší než maximální_součet, maximální_součet stává se 4.

Krok 3) Na indexu 1 je hodnota -2. Takže, aktuální_součet = 4 + (-2) = 2.

Tentokrát aktuální_součet je méně než maximální_součetV důsledku toho je hodnota maximální_součet není aktualizován.

Krok 4) Další hodnota je 1. Přičteme ji k aktuální_součet dává 3. Protože maximální_součet (4) je stále větší než aktuální_součet, maximální_součet není aktualizován.

Krok 5) Na indexu 3 je hodnota 3. Zvyšování aktuální_součet o 3 dává aktuální_součet = 6.

V tomto případě, maximální_součet je menší než aktuální_součet, Takže maximální_součet je aktualizován o hodnotu aktuální_součet.

Krok 6) Pro poslední prvek pole máme -1. Jeho sečtení k aktuální_součet dává 5, což je menší než maximální_součet. Tak, maximální_součet zůstává 6.

Jakmile jsme dosáhli konce pole, algoritmus zde končí. Nyní, maximální_součet obsahuje maximální součet, který je 6. Podpole je {4, -2, 1, 3}.

Nepravý Code pro Kadaneův algoritmus

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++ Implementace Kadaneova algoritmu

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

Výstup:

largest sum is 12

Python Implementace Kadaneova algoritmu

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

Výstup:

largest sum is 12

Analýza složitosti pro souvislé dílčí pole s největším součtem

Jednoduchý přístup používá dvě smyčky k výpočtu všech možných součtů podpolí a nalezení největšího z nich. Jedná se o přístup hrubé síly; každá smyčka běží až do konce řada, přičemž O(N²) čas.

Kadaneův algoritmus používá pouze jednu smyčku, což dává O(N) času a O(1) prostoru navíc. Na poli o 100 prvcích provede jednoduchý přístup 100 × 100 = 10 000 operací, zatímco Kadaneův provede pouze 100 – což je dramatické zrychlení pro velké vstupy.

Nejčastější dotazy