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.
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:
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.
Í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:
Í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ő:
Í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.
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.
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.
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.
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.
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.