Kadenceov algoritam: Susjedni podniz s najvećim zbrojem

Koji je najveći sum susjednog podniza?

Podniz je kontinuirani dio niza. To može biti jedan element niza ili neki dio niza. Susjedni podniz najvećeg zbroja znači podniz koji ima najveću vrijednost zbroja.

Na primjer, uzmite niz {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Njegovi podnizovi mogu biti {-10, 5, 1, 6}, {5, 1, 6} ili {2, -7, 3, -5} i tako dalje. Međutim, {5, 1, 6, 3} ne može biti podniz jer elementi nisu u susjednom nizu.

Ako primijetite, među svim podnizovima, istaknuti podniz {5, 1, 6} ima maksimalnu vrijednost zbrajanja:

Zbroj podniza {5, 1, 6} je 12, što je maksimalni zbroj svih mogućih podnizova gornjeg niza. Dakle, za ovaj niz, maksimalni zbroj susjednog podniza je {5, 1, 6}.

Jednostavan pristup rješavanju susjednog podniza s najvećim zbrojem

Jednostavan način rješavanja ovog problema je korištenje dvije petlje za pronalaženje svih podnizova, izračunavanje zbroja, a zatim pronalaženje njegove maksimalne vrijednosti.

Evo dijagrama toka za jednostavan pristup pronalaženju najvećeg zbroja susjednog podniza. Ovo je pristup grube sile, jer prolazimo kroz svaki mogući podniz.

Evo jednostavnih koraka za to.

Korak 1) inicijalizirati maks_zbroj s minimalnom cjelobrojnom vrijednošću i skupom krene i kraj na nulu.

Korak 2) Dopustite da vas i i j biti indeksi polja gdje j je veće ili jednako i; i označava početak podniza i j njegov kraj.

Korak 3) trenutni_zbroj sadrži tekući zbroj. Nakon svakog ažuriranja, provjerite je li trenutni_zbroj je veći od maks_zbroj.

Korak 4) If trenutni_zbroj je veći, zamijenite maks_zbroj s njom.

Korak 5) Kada j dođe do kraja niza, inkrement i i resetirati trenutni_zbroj na 0.

Korak 6) Ponavljajte dok i dođe do kraja niza. maks_zbroj tada sadrži najveću sumu podniza.

Nadimak Code za jednostavan pristup

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

C++ Implementacija jednostavnog pristupa

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

Izlaz:

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

Python Implementacija jednostavnog pristupa

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)

Izlaz:

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

Kadaneov algoritam za pronalaženje najvećeg zbroja susjednog podniza

Kadaneov algoritam je metoda dinamičkog programiranja koja koristi jednu petlju umjesto dvije. Obrađuje nizove s miješanim pozitivnim i negativnim brojevima, sve dok je barem jedna vrijednost nenegativna.

Trebaju nam samo dvije varijable da bismo pronašli najveću sumu susjednog podniza. Evo dijagrama toka:

Evo koraka za Kadaneov algoritam:

Korak 1) Stvorite dvije varijable, trenutni_zbroj i maks_zbroj.

trenutni_zbroj zadržava maksimalnu sumu koja završava na određenom indeksu polja, dok maks_zbroj pohranjuje najveću do sada opaženu vrijednost zbrajanja.

Korak 2) Dodaj svaki element niza u trenutni_zbrojZatim provjerite dva uvjeta u nastavku:

• If trenutni_zbroj je manji od trenutnog elementa, tada trenutni_zbroj postaje trenutni element.
• If maks_zbroj je manje od trenutni_zbroj, A zatim maks_zbroj postaje trenutni_zbroj.

Korak 3) Nakon ponavljanja prethodnog koraka za cijeli niz, maks_zbroj sadrži najveću sumu susjednog podniza.

Primjer Kadaneovog algoritma

Demonstriramo Kadaneov algoritam na malom nizu i prolazimo kroz svaki korak pronalaženja najveće sume susjednog podniza.

Pretpostavimo da je zadani niz ovakav:

Evo koraka Kadaneovog algoritma:

Korak 1) Stvorite dvije varijable, trenutni_zbroj i maks_zbrojDodijeli INT_MIN za maks_zbroj i nula do trenutni_zbrojOvdje INT_MIN predstavlja minimalnu cjelobrojnu vrijednost.

Korak 2) Na indeksu 0, vrijednost je 4. Dakle, trenutni_zbroj = 0 + 4 = 4. Budući da trenutni_zbroj je veći od maks_zbroj, maks_zbroj postaje 4.

Korak 3) Na indeksu 1, vrijednost je -2. Dakle, trenutni_zbroj = 4 + (-2) = 2.

Ovaj put trenutni_zbroj je manje od maks_zbrojKao rezultat toga, vrijednost maks_zbroj nije ažuriran.

Korak 4) Sljedeća vrijednost je 1. Dodavanjem u trenutni_zbroj daje 3. Budući da maks_zbroj (4) je još uvijek veći od trenutni_zbroj, maks_zbroj nije ažuriran.

Korak 5) Na indeksu 3, vrijednost je 3. Povećanje trenutni_zbroj za 3 daje trenutni_zbroj = 6.

U ovom slučaju, maks_zbroj je manji od trenutni_zbroj, Tako da maks_zbroj ažurira se s vrijednošću od trenutni_zbroj.

Korak 6) Za posljednji element niza imamo -1. Dodavanjem u trenutni_zbroj daje 5, što je manje od maks_zbroj, Tako, maks_zbroj ostaje 6.

Kako smo došli do kraja niza, algoritam ovdje završava. Sada, maks_zbroj sadrži maksimalnu sumu, koja je 6. Podniz je {4, -2, 1, 3}.

Nadimak Code za Kadaneov algoritam

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++ Implementacija Kadaneovog algoritma

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

Izlaz:

largest sum is 12

Python Implementacija Kadaneovog algoritma

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

Izlaz:

largest sum is 12

Analiza složenosti za najveći sumski kontinuirani podniz

Jednostavan pristup koristi dvije petlje za izračunavanje svake moguće sume podniza i lociranje najveće. To je pristup grube sile; svaka petlja se izvršava do kraja poredak, dajući O(N²) vrijeme.

Kadaneov algoritam koristi samo jednu petlju, što daje O(N) vremena i O(1) dodatnog prostora. Na nizu od 100 elemenata jednostavan pristup izvodi 100 × 100 = 10 000 operacija, dok Kadaneov izvodi samo 100 - dramatično ubrzanje za velike ulaze.

Pitanja i odgovori