Kadence'i algoritm: suurim summa külgnev alamjoon

Mis on suurima summaga külgnev alammassiiv?

Alammassiiviks on massiivi pidev osa. See võib olla üks massiivi element või osa massiivist. Suurim summa külgnev alamriba tähendab alamriba, millel on maksimaalne summa väärtus.

Näiteks võtame massiivi {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Selle alammassiivid võivad olla {-10, 5, 1, 6}, {5, 1, 6} või {2, -7, 3, -5} jne. {5, 1, 6, 3} ei saa aga olla alammassiiv, kuna elemendid ei ole pidevas järjestuses.

Kui märkate, et kõigi alammassiivide seas on esiletõstetud alammassiivil {5, 1, 6} maksimaalne summeerimisväärtus:

Alammassiivi {5, 1, 6} summa on 12, mis on ülaltoodud massiivi kõigi võimalike alammassiivide maksimaalne summa. Seega on selle massiivi puhul külgneva alammassiivi maksimaalne summa {5, 1, 6}.

Lihtne lähenemine suurima summaga külgneva alammassiivi lahendamiseks

Lihtne viis selle probleemi lahendamiseks on kasutada kahte silmust, et leida kõik alamribad, arvutada summa ja seejärel leida selle maksimaalne väärtus.

Siin on vooskeem lihtsa lähenemisviisi jaoks suurima summaga külgneva alammassiivi leidmiseks. See on toore jõu meetod, kuna me käime läbi kõik võimalikud alammassiivid.

Siin on lihtsad sammud selle tegemiseks.

Step 1) Initsialiseerida max_summa minimaalse täisarvuga ja seatud alustama ja lõpp nullini.

Step 2) Laskma i ja j olema massiivi indeksid, kus j on suurem või võrdne i; i tähistab alammassiivi algust ja j selle lõpp.

Step 3) praegune_summa hoiab jooksvat summat. Pärast iga värskendust kontrollige, kas praegune_summa on suurem kui max_summa.

Step 4) If praegune_summa on suurem, asenda max_summa ta.

Step 5) Kui j jõuab massiivi lõppu, suurendatakse i ja lähtestage praegune_summa kuni 0.

Step 6) Korda kuni i jõuab massiivi lõppu. max_summa siis hoiab suurimat alammassiivi summat.

Pseudo Code lihtsa lähenemisviisi jaoks

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        store the maximum subArray
    return the maximum sum

C++ Lihtsa lähenemise rakendamine

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

Väljund:

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

Python Lihtsa lähenemise rakendamine

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)

Väljund:

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

Kadane'i algoritm suurima summaga külgneva alammassiivi leidmiseks

Kadane'i algoritm on dünaamilise programmeerimise meetod, mis kasutab kahe tsükli asemel ühte. See käsitleb segatud positiivsete ja negatiivsete arvudega massiive, kui vähemalt üks väärtus on mittenegatiivne.

Suurima summaga külgneva alammassiivi leidmiseks on vaja ainult kahte muutujat. Siin on vooskeem:

Siin on Kadane'i algoritmi juhised:

Step 1) Loo kaks muutujat, praegune_summa ja max_summa.

praegune_summa hoiab maksimaalset summat, mis lõpeb kindla massiiviindeksiga, samal ajal kui max_summa salvestab seni vaadeldud suurima summeerimisväärtuse.

Step 2) Lisage iga massiivi element praegune_summaSeejärel kontrollige kahte allolevat tingimust:

• If praegune_summa on väiksem kui praegune element, siis praegune_summa saab praeguseks elemendiks.
• If max_summa on vähem kui praegune_summa, Siis max_summa muutub praegune_summa.

Step 3) Pärast eelmise sammu kordamist kogu massiivi jaoks, max_summa hoiab suurima summaga külgnevat alammassiivi.

Kadane'i algoritmi näide

Me demonstreerime Kadane algoritmi väikesel massiivil ja käime läbi iga sammu suurima summaga külgneva alammassiivi leidmiseks.

Oletame, et antud massiiv on umbes selline:

Siin on Kadane'i algoritmi sammud:

Step 1) Loo kaks muutujat, praegune_summa ja max_summaMäärake INT_MIN väärtuseks max_summa ja nullist praegune_summaSiin tähistab INT_MIN minimaalset täisarvu väärtust.

Step 2) Indeksi 0 juures on väärtus 4. Seega praegune_summa = 0 + 4 = 4. Kuna praegune_summa on suurem kui max_summa, max_summa saab 4.

Step 3) Indeksi 1 juures on väärtus -2. Seega praegune_summa = 4 + (-2) = 2.

Seekord praegune_summa on vähem kui max_summaSelle tulemusel on väärtus max_summa ei ole uuendatud.

Step 4) Järgmine väärtus on 1. Selle lisamine praegune_summa annab 3. Kuna max_summa (4) on ikka suurem kui praegune_summa, max_summa ei ole uuendatud.

Step 5) Indeksi 3 juures on väärtus 3. Suurendamine praegune_summa 3 annab praegune_summa = 6.

Sel juhul, max_summa on väiksem kui praegune_summanii max_summa uuendatakse väärtusega praegune_summa.

Step 6) Massiivi viimase elemendi jaoks on meil -1. Lisades selle praegune_summa annab 5, mis on väiksem kui max_summa. Niisiis, max_summa jääb alles 6.

Massiivi lõppu jõudes lõpeb algoritm siin. Nüüd, max_summa sisaldab maksimaalset summat, mis on 6. Alammassiiv on {4, -2, 1, 3}.

Pseudo Code Kadane'i algoritmi jaoks

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'i algoritmi rakendamine

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

Väljund:

largest sum is 12

Python Kadane'i algoritmi rakendamine

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

Väljund:

largest sum is 12

Suurima summa külgneva alamriba keerukuse analüüs

Lihtsustatud meetod kasutab kahte tsüklit iga võimaliku alammassiivi summa arvutamiseks ja suurima leidmiseks. See on toore jõu meetod; iga tsükkel kestab massiivi lõpuni. massiivi, andes O(N²) aega.

Kadane'i algoritm kasutab ainult ühte tsüklit, mis annab O(N) aega ja O(1) lisaruumi. 100 elemendiga massiivi puhul teeb lihtne lähenemine 100 × 100 = 10 000 operatsiooni, samas kui Kadane'i oma teeb ainult 100 – see on suurte sisendite puhul dramaatiline kiirendus.

KKK