Kadencen algoritmi: Suurin Summa Contiguous Subray

Mikä on suurin summa vierekkäin?

Alijoukko on taulukon jatkuva osa. Se voi olla taulukon yksittäinen elementti tai osa taulukosta. Suurin summa vierekkäinen alitaulukko tarkoittaa alitaulukkoa, jolla on suurin summa.

Esimerkiksi taulukko on {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Sen alitaulukot voivat olla: {-10,5,1,6} tai {5,1,6} tai {2,7,3, -5} jne. Mutta {5,1,6,3} ei voi olla subarray, koska ne eivät ylläpidä sekvenssejä.

Jos huomaat, kaikkien aliryhmien joukossa seuraavalla korostetulla alitaulukolla (5,1,6) on suurin summausarvo:

Alitaulukon summa {5,1,6} = 11, on suurin summa yllä olevan taulukon kaikissa mahdollisissa alitaulukon yhdistelmissä. Yllä olevan taulukon suurin alitaulukko on siis {5,1,6}.

Kadencen algoritmi: Suurin Summa Contiguous Subray

Yksinkertainen tapa ratkaista suurimman summan vierekkäinen alitaulukko

Yksinkertainen tapa ratkaista tämä ongelma on käyttää kahta silmukkaa kaikkien aliryhmien etsimiseen, summan laskemiseen ja sen maksimiarvon löytämiseen.

Tässä on vuokaavio yksinkertaisesta tapasta löytää suurimman summan vierekkäinen alitaulukko. Tämä on raa'an voiman lähestymistapa, koska käymme läpi kaikki mahdolliset osat.

Tässä on yksinkertaiset vaiheet.

Vaihe 1) Alusta max_sum minimikokonaisluvulla ja määritä muuttujat "begin" ja "end" nollalla.

Vaihe 2) Olkoon i ja j taulukon indeksi, jossa "j" on suurempi kuin "i". Se edustaa alitaulukon alkuindeksiä ja "j" edustaa alitaulukon loppuindeksiä.

Vaihe 3) "Current_sum" sisältää alitaulukon summan. Kun olet laskenut nykyisen summan, tarkista, onko nykyinen_summa suurempi kuin max_sum.

Vaihe 4) Jos nykyinen_summa on suurempi, korvaa max_sum nykyisellä summalla.

Vaihe 5) Tarkista, saavuttaako "j" taulukon lopun vai ei. Jos "j" saavuttaa taulukon lopun, lisää sitten "i" ja muuta nykyinen_summa arvoksi 0.

Vaihe 6) Suorita kaikki nämä vaiheet, kunnes "i" saavuttaa taulukon lopun.

Vaihe 7) Näiden kahden silmukan lopussa max_sum sisältää suurimman alitaulukon summan.

Pseudokoodi yksinkertaiselle lähestymistavalle

  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++ Yksinkertaisen lähestymistavan käyttöönotto

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

lähtö:

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

Python Yksinkertaisen lähestymistavan toteutus

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)

lähtö:

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

Kadanen algoritmi suurimman summan vierekkäisen aliryhmän löytämiseksi

Kadanen algoritmi on eräänlainen "dynaamisen ohjelmoinnin" menetelmä. Tässä käytetään yhtä silmukkaa kahden silmukan sijasta. Kadanen algoritmin yleinen toteutus toimii vain positiivisille lukutaulukoille.

Tarvitsemme vain kaksi muuttujaa löytääksemme suurimman summan vierekkäisen alitaulukon. Tässä on Kadanen algoritmin vuokaavio:

Tässä ovat Kadanen algoritmin vaiheet:

Vaihe 1) Luo kaksi muuttujaa, current_sum ja max_sum.

"Current_sum" säilyttää enimmäissumman arvon, joka päättyy tiettyyn taulukkoindeksiin, kun taas "max_sum" tallentaa suurimman summausarvon tähän mennessä.

Vaihe 2) Lisäämme arvon nykyisen_summan kanssa jokaiselle taulukon elementille. Sitten tarkistamme kaksi ehtoa alla:

• Jos current_sum on pienempi kuin nykyinen elementti, nykyinen_summa-arvo on nykyinen elementti.
• Jos max_sum on pienempi kuin nykyinen_summa, niin max_sum on nykyinen_summa.

Vaihe 3) Suorittamalla edellisen vaiheen koko taulukolle, meillä on suurin summa vierekkäinen alitaulukko "max_sum"-muuttujassa.

Esimerkki Kadanen algoritmista

Esittelemme Kadanesin algoritmia pienikokoisella taulukolla ja keskustelemme jokaisesta vaiheesta löytääksesi suurimman summan vierekkäisen alitaulukon.

Oletetaan, että annettu matriisi on seuraavanlainen:

Tässä ovat Kadanen algoritmin vaiheet:

Vaihe 1) Luo kaksi muuttujaa, current_sum ja max_sum. Määritä INT_MIN arvoon max_sum ja nolla arvoon nykyinen_summa. (Tässä INT_MIN tarkoittaa vähimmäiskokonaislukua).

Vaihe 2) Indeksillä 0 arvo on 4. Eli nykyinen_summa = 0 + 4 tai 4. Tässä nykyinen_summa on suurempi kuin max_sum, max_sum on 4.

Vaihe 3) Indeksillä 1 arvo on -2. Joten nykyinen_summa = 4 + (-2) tai 2.

Tällä kertaa nykyinen_summa on pienempi kuin max_sum. Tämän seurauksena max_sum-arvoa ei päivitetä.

Vaihe 4) Seuraava arvo on 1. Jos lisäämme tämän nykyisen_summan kanssa, niin nykyinen_summa on 3. Silti max_sum on suurempi kuin nykyinen_summa. Joten, max_sum ei päivity.

Vaihe 5) Indeksillä 3 arvo on kolme. Päivitämme arvon lisäämällä arvoa current_sum 3:lla. Nykyinen_summa on siis 6.

Tässä tapauksessa max_sum on pienempi kuin nykyinen_summa. Joten max_sum päivitetään nykyisen_summan arvolla.

Vaihe 6) Matriisin viimeiselle elementille meillä on -1. Jos lisäämme tämän nykyisen_summan kanssa, nykyinen_summa on 5, mikä on pienempi kuin max_sum. Joten max_sum pysyy 6:na.

Kun saavuimme taulukon loppuun, algoritmi päättyy tähän. Nyt "max_sum" sisältää enimmäissumma-alitaulukon. Mikä on 5. Alitaulukko on {4,-2,1,3}.

Pseudokoodi Kadanen algoritmille

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++Kadanen algoritmin toteutus

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

lähtö:

largest sum is 12

Python Kadanen algoritmin toteutus

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

lähtö:

largest sum is 12

Monimutkaisuusanalyysi suurimman summan vierekkäiselle alialueelle

Yksinkertainen lähestymistapa käyttää kahta silmukkaa. Tämä menetelmä laskee kaikki mahdolliset alijoukon summat löytääkseen suurimman. Se on raa'an voiman lähestymistapa. Jokainen silmukka kestää osan loppuun ryhmä.

Jos taulukossa on yhteensä N elementtejä, käytämme kahta silmukkaa N:n läpi² elementtejä. Tämän seurauksena yksinkertaisen lähestymistavan aika monimutkaisuus löytää suurimman summan vierekkäinen aliryhmä O(N2). Tässä "O" tarkoittaa monimutkaisuusfunktiota.

Toisaalta Kadanen algoritmi on dynaaminen ohjelmointimenetelmä suurimman vierekkäisen summa-alitaulukon löytämiseksi. Jos noudatat esimerkkiä tai koodia, huomaat, että käytämme vain yhtä silmukkaa.

Tämän seurauksena, jos syöttötaulukon koko on N, silloin Kadanen algoritmin aikamonimutkaisuus on O(N). Tämä on nopeampaa kuin yksinkertainen lähestymistapa. Esimerkiksi matriisi, joka sisältää 100 elementtiä. Yksinkertainen lähestymistapa vie 100 * 100 tai 10,000 100 CPU aikaa. Mutta Kadanen algoritmi vie vain XNUMX CPU aikaa.