Kadencen algoritmi: Suurin Summa Contiguous Subray

Mikä on suurin summa yhtenäinen alitaulukko?

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.

Otetaan esimerkiksi taulukko {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Sen alitaulukot voivat olla {-10, 5, 1, 6}, {5, 1, 6} tai {2, -7, 3, -5} ja niin edelleen. {5, 1, 6, 3} ei kuitenkaan voi olla alitaulukko, koska elementit eivät ole yhtenäisessä järjestyksessä.

Jos huomaat, kaikkien alitaulukoiden joukossa korostetulla alitaulukolla {5, 1, 6} on suurin summa-arvo:

Alitaulukon {5, 1, 6} summa on 12, mikä on suurin summa yllä olevan taulukon kaikkien mahdollisten alitaulukoiden välillä. Joten tässä taulukossa yhtenäisen alitaulukon suurin summa on {5, 1, 6}.

Yksinkertainen lähestymistapa suurimman summan vierekkäisen alitaulukon ratkaisemiseen

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 lähestymistavasta suurimman summaisen yhtenäisen alitaulukon löytämiseksi. Tämä on raa'an voiman lähestymistapa, koska käymme läpi kaikki mahdolliset alitaulukot.

Tässä on yksinkertaiset vaiheet.

Vaihe 1) Alustaa maksimisumma pienimmällä kokonaislukuarvolla ja aseta alkaa ja loppu nollaan.

Vaihe 2) Antaa i ja j olla taulukkoindeksejä, joissa j on suurempi tai yhtä suuri kuin i; i merkitsee alitaulukon alkua ja j sen loppu.

Vaihe 3) nykyinen_summa sisältää juoksevan summan. Tarkista jokaisen päivityksen jälkeen, onko nykyinen_summa on suurempi kuin maksimisumma.

Vaihe 4) If nykyinen_summa on suurempi, korvaa maksimisumma sen kanssa.

Vaihe 5) Kun j saavuttaa taulukon lopun, lisää i ja nollaa nykyinen_summa on 0.

Vaihe 6) Toista, kunnes i saavuttaa taulukon lopun. maksimisumma sisältää sitten suurimman alitaulukon summan.

Pseudo Code yksinkertaiseen lähestymistapaan

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        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 käyttöönotto

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 löytämiseksi yhtenäisessä alitaulukossa

Kadanen algoritmi on dynaaminen ohjelmointimenetelmä, joka käyttää yhtä silmukkaa kahden sijaan. Se käsittelee taulukoita, joissa on sekä positiivisia että negatiivisia lukuja, kunhan vähintään yksi arvo on ei-negatiivinen.

Tarvitsemme vain kaksi muuttujaa löytääksemme suurimman summaisen yhtenäisen alitaulukon. Tässä on vuokaavio:

Tässä ovat Kadanen algoritmin vaiheet:

Vaihe 1) Luo kaksi muuttujaa, nykyinen_summa ja maksimisumma.

nykyinen_summa pitää suurimman summan, joka päättyy tiettyyn taulukkoindeksiin, kun taas maksimisumma tallentaa tähän mennessä havaitun suurimman summa-arvon.

Vaihe 2) Lisää jokainen taulukon elementti nykyinen_summaTarkista sitten alla olevat kaksi ehtoa:

• If nykyinen_summa on pienempi kuin nykyinen elementti, niin nykyinen_summa tulee nykyiseksi elementiksi.
• If maksimisumma on vähemmän kuin nykyinen_summa, sitten maksimisumma tulee nykyinen_summa.

Vaihe 3) Kun edellinen vaihe on toistettu koko taulukolle, maksimisumma sisältää suurimman summaisen yhtenäisen alitaulukon.

Esimerkki Kadanen algoritmista

Esittelemme Kadanen algoritmin pienellä taulukolla ja käymme läpi jokaisen vaiheen suurimman summaisen yhtenäisen alitaulukon löytämiseksi.

Oletetaan, että annettu taulukko on seuraavanlainen:

Kadanen algoritmin vaiheet ovat seuraavat:

Vaihe 1) Luo kaksi muuttujaa, nykyinen_summa ja maksimisumma. Määritä INT_MIN-arvoksi maksimisumma ja nollasta nykyinen_summaTässä INT_MIN edustaa pienintä kokonaislukuarvoa.

Vaihe 2) Indeksissä 0 arvo on 4. Joten, nykyinen_summa = 0 + 4 = 4. Koska nykyinen_summa on suurempi kuin maksimisumma, maksimisumma tulee 4.

Vaihe 3) Indeksin 1 kohdalla arvo on -2. Joten, nykyinen_summa = 4 + (-2) = 2.

Tällä kertaa nykyinen_summa on vähemmän kuin maksimisummaTämän seurauksena arvo maksimisumma ei ole päivitetty.

Vaihe 4) Seuraava arvo on 1. Lisäämällä sen nykyinen_summa antaa 3. Koska maksimisumma (4) on edelleen suurempi kuin nykyinen_summa, maksimisumma ei ole päivitetty.

Vaihe 5) Indeksissä 3 arvo on 3. Kasvava nykyinen_summa 3 antaa nykyinen_summa = 6.

Tässä tapauksessa, maksimisumma on pienempi kuin nykyinen_summa, Niin maksimisumma päivitetään arvolla nykyinen_summa.

Vaihe 6) Taulukon viimeiselle alkiolle saadaan -1. Lisäämme sen nykyinen_summa antaa 5, joka on pienempi kuin maksimisumma. Niin, maksimisumma jäljellä 303 305 534.

Kun saavutimme taulukon lopun, algoritmi päättyy tähän. Nyt, maksimisumma sisältää suurimman summan, joka on 6. Alitaulukko on {4, -2, 1, 3}.

Pseudo Code Kadanen algoritmille

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

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

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 kaikkien mahdollisten alitaulukon summien laskemiseen ja suurimman löytämiseen. Se on raa'an voiman lähestymistapa; jokainen silmukka jatkuu taulukon loppuun. ryhmä, antaa O(N²) ajan.

Kadanen algoritmi käyttää vain yhtä silmukkaa, mikä antaa O(N) aikaa ja O(1) lisätilaa. 100 elementin taulukolla yksinkertainen lähestymistapa suorittaa 100 × 100 = 10 000 operaatiota, kun taas Kadanen algoritmi suorittaa vain 100 – dramaattinen nopeus suurilla syötteillä.

UKK