Algorytm Kadence'a: ciągła podtablica o największej sumie

Jaka jest największa suma sąsiadujących podtablic?

Podtablica jest ciągłą częścią tablicy. Może to być pojedynczy element tablicy lub część tablicy. Ciągła podtablica o największej sumie oznacza podtablicę, która ma maksymalną wartość sumy.

Na przykład tablica to {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Jej tablicami podrzędnymi mogą być: {-10,5,1,6} lub {5,1,6} lub {2,7,3, -5} itd. Ale {5,1,6,3} nie może być podtablicę, ponieważ nie zachowują sekwencji.

Zauważ, że spośród wszystkich podtablic, następująca wyróżniona podtablica (5,1,6) ma maksymalną wartość sumy:

Suma podtablicy {5,1,6} = 11, jest maksymalną sumą wszystkich możliwych kombinacji podtablicy powyższej tablicy. Zatem dla powyższej tablicy maksymalna podtablica to {5,1,6}.

Algorytm Kadence'a: ciągła podtablica o największej sumie

Proste podejście do rozwiązywania ciągłej podtablicy o największej sumie

Prostym sposobem rozwiązania tego problemu jest użycie dwóch pętli w celu znalezienia wszystkich podtablic, obliczenia sumy, a następnie znalezienia jej maksymalnej wartości.

Oto schemat prostego podejścia do znajdowania ciągłej podtablicy o największej sumie. Jest to podejście oparte na brutalnej sile, ponieważ przeglądamy wszystkie możliwe podtablice.

Oto proste kroki, jak to zrobić.

Krok 1) Zainicjuj max_sum minimalną wartością całkowitą i przypisz zmiennym „begin” i „end” zerem.

Krok 2) Niech i oraz j będą indeksami tablicy, gdzie „j” jest większe niż równe „i”. Reprezentuje początkowy indeks podtablicy, a „j” oznacza końcowy indeks podtablicy.

Krok 3) „Current_sum” będzie zawierać sumę podtablicy. Po obliczeniu sumy bieżącej sprawdź, czy suma_bieżąca jest większa niż suma_maksymalna.

Krok 4) Jeśli bieżąca_suma jest większa, zastąp maksymalną_sumę bieżącą sumą.

Krok 5) Sprawdź, czy „j” osiąga koniec tablicy, czy nie. Jeśli „j” osiągnie koniec tablicy, zwiększ „i” i zmień wartość bieżącej sumy na 0.

Krok 6) Wykonaj wszystkie te kroki, aż „i” osiągnie koniec tablicy.

Krok 7) Na końcu tych dwóch pętli, max_sum będzie zawierać największą sumę podtablicy.

Pseudokod prostego podejścia

  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++ Implementacja prostego podejścia

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

Wyjście:

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

Python Implementacja prostego podejścia

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)

Wyjście:

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

Algorytm Kadane’a służący do znajdowania ciągłej podtablicy o największej sumie

Algorytm Kadane'a jest rodzajem metody „programowania dynamicznego”. Tutaj użyjemy jednej pętli zamiast dwóch. Ogólna implementacja algorytmu Kadane'a działa tylko w przypadku tablic liczb dodatnich.

Potrzebujemy tylko dwóch zmiennych, aby znaleźć ciągłą podtablicę o największej sumie. Oto schemat blokowy algorytmu Kadane'a:

Oto kroki algorytmu Kadane’a:

Krok 1) Utwórz dwie zmienne: current_sum i max_sum.

„Current_sum” zachowa wartość maksymalnej sumy kończącej się na określonym indeksie tablicy, podczas gdy „max_sum” będzie przechowywać dotychczasową maksymalną wartość sumy.

Krok 2) Dodamy wartość z current_sum dla każdego elementu tablicy. Następnie sprawdzimy dwa warunki poniżej:

• Jeśli wartość current_sum jest mniejsza niż bieżący element, wówczas wartość current_sum będzie bieżącym elementem.
• Jeśli max_sum jest mniejsza niż current_sum, wówczas max_sum będzie bieżącym_sumem.

Krok 3) Wykonując poprzedni krok dla całej tablicy, będziemy mieli największą sumę ciągłą podtablicy w zmiennej „max_sum”.

Przykład algorytmu Kadane’a

Zademonstrujemy algorytm Kadanesa z tablicą o małych rozmiarach i omówimy każdy etap znajdowania ciągłej podtablicy o największej sumie.

Załóżmy, że dana tablica wygląda następująco:

Oto kroki algorytmu Kadane’a:

Krok 1) Utwórz dwie zmienne, current_sum i max_sum. Przypisz INT_MIN do max_sum i zero do current_sum. (Tutaj INT_MIN oznacza minimalną liczbę całkowitą).

Krok 2) Przy indeksie 0 wartość wynosi 4. Zatem suma_bieżąca = 0 + 4 lub 4. Tutaj suma_bieżąca jest większa niż suma_maksymalna, suma_bieżąca będzie wynosić 4.

Krok 3) Przy indeksie 1 wartość wynosi -2. Zatem bieżąca suma = 4 + (-2) lub 2.

Tym razem current_sum jest mniejsza niż max_sum. W rezultacie wartość max_sum nie zostanie zaktualizowana.

Krok 4) Następna wartość to 1. Jeśli dodamy to do sumy_bieżącej, suma_bieżąca będzie wynosić 3. Mimo to suma_maksymalna jest większa niż suma_bieżąca. Zatem max_sum nie zostanie zaktualizowany.

Krok 5) Przy indeksie 3 wartość wynosi trzy. Zaktualizujemy wartość, zwiększając bieżącą_sumę o 3. Zatem bieżąca_suma będzie wynosić 6.

W tym przypadku max_sum jest mniejsza niż current_sum. Zatem max_sum zostanie zaktualizowana o wartość current_sum.

Krok 6) Dla ostatniego elementu tablicy mamy -1. Jeśli dodamy to do sumy_bieżącej, suma_bieżąca będzie wynosić 5, czyli jest mniejsza niż suma_maksymalna. Zatem max_sum pozostanie 6.

Gdy dotarliśmy do końca tablicy, algorytm kończy się w tym miejscu. Teraz „max_sum” zawiera podtablicę sumy maksymalnej. Czyli 5. Podtablica to {4,-2,1,3}.

Pseudokod algorytmu Kadane'a

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++Implementacja algorytmu Kadane’a

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

Wyjście:

largest sum is 12

Python Implementacja algorytmu Kadane’a

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

Wyjście:

largest sum is 12

Analiza złożoności dla największej sumy ciągłej podtablicy

Proste podejście wykorzystuje dwie pętle. Ta metoda oblicza wszystkie możliwe sumy podtablic, aby znaleźć największą. To podejście oparte na brutalnej sile. Każda pętla biegnie do końca szyk.

Jeśli tablica ma w sumie N elementów, to za pomocą dwóch pętli przejdziemy przez N² elementów. W rezultacie złożoność czasowa prostego podejścia do znalezienia największej sumy ciągłej podtablicy będzie wynosić O(N2). Tutaj „O” oznacza funkcję złożoności.

Z drugiej strony algorytm Kadane’a jest metodą programowania dynamicznego służącą do znajdowania maksymalnej ciągłej podtablicy sumy. Jeśli zastosujesz się do przykładu lub kodu, zobaczysz, że używamy tylko jednej pętli.

W rezultacie, jeśli tablica wejściowa ma rozmiar N, to złożoność czasowa algorytmu Kadane'a będzie wynosić O(N). Jest to szybsze niż proste podejście. Na przykład tablica zawierająca 100 elementów. Proste podejście zajmie 100*100 lub 10,000 100 czasu procesora. Ale algorytm Kadane'a zajmie tylko XNUMX czasu procesora.