Kadenceův algoritmus: Souvislé dílčí pole s největším součtem
Jaký je největší součet souvislého podpole?
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.
Pole je například {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Jeho podpole mohou být: {-10,5,1,6} nebo {5,1,6} nebo {2,7,3, -5} atd. Ale {5,1,6,3} nemůže být subarray, protože neudržují sekvence.
Pokud si všimnete, že mezi všemi podpolemi má následující zvýrazněné podpole (5,1,6) maximální hodnotu součtu:
Součet dílčího pole {5,1,6} = 11 je maximální součet ve všech možných kombinacích dílčího pole výše uvedeného pole. Takže pro výše uvedené pole je maximální podpole {5,1,6}.
Kadenceův algoritmus: Souvislé dílčí pole s největším součtem
Jednoduchý přístup k řešení souvislého podpole s největším součtem
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 pro jednoduchý přístup k nalezení největšího součtu souvislého dílčího pole. Toto je přístup hrubou silou, protože procházíme všemi možnými podskupinami.
Zde jsou jednoduché kroky, jak toho dosáhnout.
Krok 1) Inicializujte max_sum s minimální celočíselnou hodnotou a přiřaďte proměnným „begin“ a „end“ nulu.
Krok 2) Nechť i a j jsou index pole, kde „j“ je větší než rovno „i“. Představuje počáteční index podpole a „j“ představuje koncový index podpole.
Krok 3) „Aktuální_součet“ bude obsahovat součet podpole. Po výpočtu aktuálního součtu zkontrolujte, zda je current_sum větší než max_sum.
Krok 4) Pokud je aktuální_součet větší, pak nahraďte maximální_součet aktuálním součtem.
Krok 5) Zkontrolujte, zda „j“ dosahuje konce pole nebo ne. Pokud „j“ dosáhne konce pole, zvyšte „i“ a změňte hodnotu current_sum na 0.
Krok 6) Proveďte všechny tyto kroky, dokud „i“ nedosáhne konce pole.
Krok 7) Na konci těchto dvou smyček bude max_sum obsahovat největší součet podpole.
Pseudokód pro jednoduchý přístup
function maximumSubarraySum(): input: array for all possible subArray from array: calculate sum of each sub array 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 k nalezení největšího součtu souvislého podpole
Kadaneův algoritmus je druh metody „dynamického programování“. Zde použijeme jednu smyčku místo dvou smyček. Obecná implementace Kadane's Algorithm funguje pouze pro kladná číselná pole.
K nalezení největšího součtu souvislého podpole potřebujeme pouze dvě proměnné. Zde je vývojový diagram pro Kadaneův algoritmus:
Zde jsou kroky pro Kadaneův algoritmus:
Krok 1) Vytvořte dvě proměnné, current_sum a max_sum.
„Current_sum“ zachová hodnotu maximálního součtu, který končí v určitém indexu pole, zatímco „max_sum“ bude ukládat dosud maximální hodnotu součtu.
Krok 2) Ke každému prvku pole přidáme hodnotu s aktuálním součtem. Poté zkontrolujeme dvě podmínky níže:
- Pokud je aktuální_součet menší než aktuální prvek, bude aktuálním prvkem hodnota current_sum.
- Pokud je max_sum menší než aktuální_součet, pak max_sum bude aktuální_součet.
Krok 3) Když provedeme předchozí krok pro celé pole, budeme mít souvislé podpole s největším součtem v proměnné „max_sum“.
Příklad Kadaneova algoritmu
Budeme demonstrovat Kadanesův algoritmus s malým polem a prodiskutujeme každý krok hledání největšího součetného souvislého podpole.
Předpokládejme, že dané pole je jako následující:
Zde jsou kroky Kadaneova algoritmu:
Krok 1) Vytvořte dvě proměnné, current_sum a max_sum. Přiřaďte INT_MIN k max_sum a nulu k current_sum. (Zde INT_MIN znamená minimální celé číslo).
Krok 2) Při indexu 0 je hodnota 4. Takže current_sum = 0 + 4 nebo 4. Zde je current_sum větší než max_sum, max_sum bude 4.
Krok 3) U indexu 1 je hodnota -2. Takže aktuální_součet = 4 + (-2) nebo 2.
Tentokrát je aktuální_součet menší než maximální_součet. V důsledku toho nebude hodnota max_sum aktualizována.
Krok 4) Další hodnota je 1. Přičteme-li to k aktuálnímu_sumu, pak aktuální_součet bude 3. Přesto je maximální_součet větší než aktuální_součet. Takže max_sum nebude aktualizován.
Krok 5) U indexu 3 je hodnota tři. Hodnotu aktualizujeme zvýšením aktuální_součet o 3. Aktuální_součet tedy bude 6.
V tomto případě je max_sum menší než current_sum. Takže max_sum bude aktualizován na hodnotu current_sum.
Krok 6) Pro poslední prvek pole máme -1. Pokud toto sečteme s aktuální_součet, aktuální_součet bude 5, což je menší než maximální_součet. Takže max_sum zůstane 6.
Když jsme dosáhli konce pole, algoritmus zde končí. Nyní „max_sum“ obsahuje podpole maximálního součtu. Což je 5. Dílčí pole je {4,-2,1,3}.
Pseudokód pro Kadaneův algoritmus
function KadaneAlgorithm(): input: array maximum_sum, current_sum = 0 for each elements 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 -10000000 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. Tato metoda vypočítá všechny možné součty dílčích polí, aby nalezla ten největší. Je to přístup hrubou silou. Každá smyčka běží až do konce řada.
Pokud má pole celkem N prvky, pak pomocí dvou smyček projdeme N2 prvky. V důsledku toho bude časová složitost pro jednoduchý přístup k nalezení největšího součtu souvislého podpole O(N2)
. Zde „O“ znamená funkci složitosti.
Na druhou stranu je Kadaneův algoritmus metodou dynamického programování k nalezení maximálního souvislého součtu podpole. Pokud budete postupovat podle příkladu nebo kódu, uvidíte, že používáme pouze jednu smyčku.
V důsledku toho, pokud má vstupní pole velikost N, pak bude časová složitost Kadaneova algoritmu O(N). To je rychlejší než jednoduchý přístup. Například pole obsahující 100 prvků. Jednoduchý přístup zabere 100*100 nebo 10,000 100 CPU času. Ale algoritmus Kadane zabere pouze XNUMX CPU času.