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.

Vegyük például a {-10, 5, 1, 6, -9, 2, -7, 3, -5} tömböt. Az altömbjei lehetnek {-10, 5, 1, 6}, {5, 1, 6} vagy {2, -7, 3, -5}, és így tovább. Azonban az {5, 1, 6, 3} nem lehet altömb, mivel az elemek nem egymás után következnek.

Ha észreveszed, az összes altömb közül a kiemelt {5, 1, 6} altömb rendelkezik a maximális összegzési értékkel:

Az {5, 1, 6} résztömb összege 12, ami a fenti tömb összes lehetséges résztömbjének maximális összege. Tehát ennél a tömbnél az összefüggő résztömbök maximális összege {5, 1, 6}.

Egyszerű megközelítés a legnagyobb összegű összefüggő résztö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 az egyszerű megközelítéshez, amellyel a legnagyobb összegű összefüggő résztömböt keressük. Ez egy nyers erő módszer, mivel minden lehetséges résztömbön végigmegyünk.

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

Step 1) inicializálása max_összeg a minimális egész értékkel és beállítva kezdődik és a végén nullára.

Step 2) Legyen i és a j legyenek tömbindexek, ahol j nagyobb vagy egyenlő i; i az altömb kezdetét jelöli, és j a vége.

Step 3) aktuális_összeg tartalmazza a futó összeget. Minden frissítés után ellenőrizze, hogy aktuális_összeg nagyobb, mint max_összeg.

Step 4) If aktuális_összeg nagyobb, cserélje ki max_összeg vele.

Step 5) Amikor j eléri a tömb végét, növelés i és nullázza aktuális_összeg A 0.

Step 6) Ismételje meg, amíg i eléri a tömb végét. max_összeg akkor a legnagyobb résztömbösszeget tartalmazza.

Pszeudo Code az egyszerű megközelítéshez

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        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 Az 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ő résztömb megtalálására

Kadane algoritmusa egy dinamikus programozási módszer, amely egyetlen ciklust használ kettő helyett. Kezeli a vegyes pozitív és negatív számokat tartalmazó tömböket, amennyiben legalább egy érték nem negatív.

Csak két változóra van szükségünk a legnagyobb összegű összefüggő résztömb megtalálásához. Íme a folyamatábra:

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

Step 1) Hozz létre két változót, aktuális_összeg és a max_összeg.

aktuális_összeg megtartja a maximális összeget, amely egy adott tömbindexnél végződik, míg max_összeg az eddig megfigyelt legnagyobb összegzett értéket tárolja.

Step 2) Adja hozzá az egyes tömbelemeket aktuális_összegEzután ellenőrizze az alábbi két feltételt:

• If aktuális_összeg kisebb, mint az aktuális elem, akkor aktuális_összeg válik az aktuális elemmé.
• If max_összeg kevesebb mint aktuális_összeg, Akkor max_összeg válik aktuális_összeg.

Step 3) Miután megismételtük az előző lépést a teljes tömbre, max_összeg a legnagyobb összegű összefüggő altömböt tartalmazza.

Példa a Kadane-algoritmusra

Egy kis tömbön bemutatjuk Kadane algoritmusát, és végigmegyünk a legnagyobb összegű összefüggő résztömb megtalálásának minden lépésén.

Tegyük fel, hogy a megadott tömb a következőhöz hasonló:

Kadane algoritmusának lépései a következők:

Step 1) Hozz létre két változót, aktuális_összeg és a max_összeg. Rendelje hozzá az INT_MIN értékét a következőhöz: max_összeg és nullától aktuális_összegItt az INT_MIN a minimális egész értéket jelöli.

Step 2) A 0. indexnél az érték 4. Tehát, aktuális_összeg = 0 + 4 = 4. Mivel aktuális_összeg nagyobb, mint max_összeg, max_összeg 4-es lesz.

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

Ezúttal aktuális_összeg kevesebb mint max_összegEnnek eredményeként a következő értéke max_összeg nincs frissítve.

Step 4) A következő érték 1. Hozzáadása aktuális_összeg 3-at ad. Mivel max_összeg (4) még mindig nagyobb, mint aktuális_összeg, max_összeg nincs frissítve.

Step 5) A 3-as indexnél az érték 3. Növekvő aktuális_összeg 3-szor ad aktuális_összeg = 6.

Ebben az esetben, max_összeg kisebb, mint aktuális_összeg, Így max_összeg értékével frissül. aktuális_összeg.

Step 6) A tömb utolsó eleméhez -1-et adunk. Hozzáadjuk aktuális_összeg 5-öt ad, ami kisebb, mint max_összeg. Így, max_összeg marad a 6.

Ahogy elértük a tömb végét, az algoritmus itt véget ér. Most, max_összeg tartalmazza a maximális összeget, ami 6. Az altömb {4, -2, 1, 3}.

Pszeudo Code Kadane algoritmusához

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element 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 -1,000,000,000
    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 ciklust használ az összes lehetséges résztömbösszeg kiszámítására és a legnagyobb megkeresésére. Ez egy nyers erő módszer; minden ciklus a tömb végéig fut. sor, adva O(N²) idő.

Kadane algoritmusa csak egyetlen ciklust használ, ami O(N) időt és O(1) plusz helyet biztosít. Egy 100 elemből álló tömbön az egyszerű megközelítés 100 × 100 = 10 000 műveletet hajt végre, míg Kadane algoritmusa csak 100-at – ami drámai gyorsulást jelent nagy bemenetek esetén.

GYIK