Kadence algoritmusa: Legnagyobb összegű összefüggő részegység

Mi a legnagyobb összegű összefüggő résztömb?

Az altömb egy tömb folytonos része. Ez lehet egy tömb egyetlen eleme vagy a tömb egy része. A legnagyobb összegű összefüggő altömb olyan altömböt jelent, amelynek a maximális összegértéke van.

Például egy tömb {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Altömbjei lehetnek: {-10,5,1,6} vagy {5,1,6} vagy {2,7,3, -5} stb. De az {5,1,6,3} nem lehet subarray, mert nem tartják karban a szekvenciákat.

Legnagyobb összegű összefüggő alrendszer

Ha észreveszi, az összes altömb közül a következő kiemelt altömb (5,1,6) rendelkezik a maximális összegzési értékkel:

Legnagyobb összegű összefüggő alrendszer

Az {5,1,6} = 11 altömb összege a fenti tömb összes lehetséges altömb kombinációjának maximális összege. Tehát a fenti tömb esetében a maximális altömb {5,1,6}.

Kadence algoritmusa: Legnagyobb összegű összefüggő részegység

Egyszerű megközelítés a legnagyobb összegű összefüggő altömb megoldására

A probléma egyszerű megoldása az, ha két hurok segítségével megkeresi az összes altömböt, kiszámítja az összeget, majd megtalálja a maximális értékét.

Íme a folyamatábra a legnagyobb összegű összefüggő altömb megtalálásának egyszerű megközelítéséhez. Ez egy brute force megközelítés, mivel minden lehetséges részterületen keresztülmegyünk.

Egyszerű megközelítés a legnagyobb összeg megoldásához

Íme az egyszerű lépések ehhez.

Step 1) Inicializálja a max_sum értéket minimális egész értékkel, és rendelje hozzá a „begin” és a „end” változókat nullához.

Step 2) Legyen i és j a tömb indexe, ahol „j” nagyobb, mint „i”. Ez az altömb kezdőindexe, a „j” pedig az altömb záró indexe.

Step 3) Az „aktuális_összeg” tartalmazza az altömb összegét. Az aktuális összeg kiszámítása után ellenőrizze, hogy az aktuális_összeg nagyobb-e, mint a max_sum.

Step 4) Ha a jelenlegi_összeg nagyobb, akkor cserélje ki a max_sum értéket az aktuális összegre.

Step 5) Ellenőrizze, hogy a „j” eléri-e a tömb végét vagy sem. Ha a „j” eléri a tömb végét, akkor növelje az „i”-t, és módosítsa az aktuális_összeg értéket 0-ra.

Step 6) Végezze el ezeket a lépéseket, amíg az „i” el nem éri a tömb végét.

Step 7) A két ciklus végén a max_sum tartalmazza a legnagyobb részösszeget.

Pszeudo kód az egyszerű megközelítéshez

  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++ Az egyszerű megközelítés megvalósítása

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

output:

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

Python Egyszerű megközelítés megvalósítása

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)

output:

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

Kadane algoritmusa a legnagyobb összegű összefüggő altömb megtalálásához

A Kadane algoritmusa egyfajta „dinamikus programozási” módszer. Itt egy hurkot fogunk használni két hurok helyett. A Kadane-algoritmus általános megvalósítása csak pozitív számtömbök esetén működik.

Csak két változóra van szükségünk, hogy megtaláljuk a legnagyobb összegű összefüggő altömböt. Íme a Kadane-algoritmus folyamatábrája:

Kadane algoritmusa a legnagyobb összeg megtalálására

Íme a Kadane-algoritmus lépései:

Step 1) Hozzon létre két változót, a current_sum és a max_sum.

A „Current_sum” megőrzi a maximális összeg értékét, amely egy adott tömbindexben végződik, míg a „max_sum” az eddigi maximális összegzési értéket tárolja.

Step 2) Minden tömbelemhez hozzáadjuk az értéket a current_sum értékkel. Ezután két feltételt ellenőrizünk alább:

  • Ha a current_sum kisebb, mint az aktuális elem, akkor a current_sum érték lesz az aktuális elem.
  • Ha a max_sum kisebb, mint az aktuális_összeg, akkor a max_sum értéke aktuális_összeg.

Step 3) Az előző lépést a teljes tömbre végrehajtva megkapjuk a legnagyobb összegű összefüggő altömböt a „max_sum” változóban.

Példa a Kadane-algoritmusra

Bemutatjuk a Kadanes-algoritmust egy kis méretű tömb segítségével, és megbeszéljük a legnagyobb összegű összefüggő altömb megtalálásának minden lépését.

Tegyük fel, hogy az adott tömb a következő:

Példa a Kadane-algoritmusra

Íme a Kadane-algoritmus lépései:

Step 1) Hozzon létre két változót, a current_sum és a max_sum. Rendelje hozzá az INT_MIN értéket a max_sum-hoz és nullát az aktuális_összeghez. (Itt az INT_MIN a minimális egész számot jelenti).

Step 2) A 0 indexnél az érték 4. Tehát az aktuális_összeg = 0 + 4 vagy 4. Itt az aktuális_összeg nagyobb, mint a max_sum, a max_sum 4 lesz.

Példa a Kadane-algoritmusra

Step 3) Az 1. indexnél az érték -2. Tehát az aktuális_összeg = 4 + (-2) vagy 2.

Ezúttal az aktuális_összeg kisebb, mint a max_sum. Ennek eredményeként a max_sum értéke nem frissül.

Példa a Kadane-algoritmusra

Step 4) A következő érték 1. Ha ezt összeadjuk az aktuális_összeggel, akkor az aktuális_összeg 3 lesz. Ennek ellenére a max_sum nagyobb, mint az aktuális_összeg. Tehát a max_sum nem frissül.

Példa a Kadane-algoritmusra

Step 5) A 3. indexnél az érték három. Frissítjük az értéket az aktuális_összeg 3-mal történő növelésével. Tehát az aktuális_összeg 6 lesz.

Példa a Kadane-algoritmusra

Ebben az esetben a max_sum kisebb, mint az aktuális_összeg. Tehát a max_sum az aktuális_összeg értékével frissül.

Step 6) A tömb utolsó eleméhez -1. Ha ezt összeadjuk az aktuális_összeggel, akkor az aktuális_összeg 5 lesz, ami kisebb, mint a max_sum. Tehát a max_sum 6 marad.

Példa a Kadane-algoritmusra

Amint a tömb végére értünk, az algoritmus itt ér véget. Most a „max_sum” tartalmazza a maximális összegű altömböt. Ami 5. Az altömb {4,-2,1,3}.

Pszeudo kód Kadane algoritmusához

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++Kadane algoritmusának megvalósítása

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

output:

largest sum is 12

Python Kadane algoritmusának megvalósítása

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

output:

largest sum is 12

Komplexitáselemzés a legnagyobb összegű összefüggő alrendszerhez

Az egyszerű megközelítés két hurkot használ. Ez a módszer kiszámítja az összes lehetséges altömb összegét, hogy megtalálja a legnagyobbat. Ez egy nyers erő megközelítés. Minden ciklus a végéig fut sor.

Ha egy tömbnek összesen van N elemeket, majd két hurok segítségével N-en megyünk át2 elemeket. Ennek eredményeként a legnagyobb összegű összefüggő altömb megtalálásának egyszerű megközelítésének időbeli bonyolultsága O(N2). Itt az „O” a komplexitási függvényt jelenti.

Másrészt a Kadane algoritmusa a dinamikus programozási módszer a maximális összefüggő összeg altömb megtalálására. Ha követi a példát vagy a kódot, látni fogja, hogy csak egy hurkot használunk.

Ennek eredményeként, ha a bemeneti tömb mérete: N, akkor a Kadane-algoritmus időbonyolultsága O(N). Ez gyorsabb, mint az egyszerű megközelítés. Például egy 100 elemet tartalmazó tömb. Az egyszerű megközelítés 100*100 vagy 10,000 100 CPU-időt vesz igénybe. De a Kadane algoritmusa csak XNUMX CPU-időt vesz igénybe.