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.

Souvislé dílčí pole s největším součtem

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:

Souvislé dílčí pole s největším součtem

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.

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

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:

Kadaneův algoritmus k nalezení největší sumy

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í:

Příklad Kadaneova algoritmu

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.

Příklad Kadaneova algoritmu

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.

Příklad Kadaneova algoritmu

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.

Příklad Kadaneova algoritmu

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.

Příklad Kadaneova algoritmu

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.

Příklad Kadaneova algoritmu

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.