Kadence Algoritması: En Büyük Toplamlı Bitişik Alt Dizi

En Büyük Toplama Değeri Olan Bitişik Alt Dizi Nedir?

Bir alt dizi, bir dizinin sürekli bir parçasıdır. Bir dizinin tek bir elemanı veya dizinin bir kısmı olabilir. En büyük toplam bitişik alt dizi, maksimum toplam değerine sahip bir alt dizi anlamına gelir.

Örneğin, {-10, 5, 1, 6, -9, 2, -7, 3, -5} dizisini ele alalım. Bu dizinin alt dizileri {-10, 5, 1, 6}, {5, 1, 6} veya {2, -7, 3, -5} ve benzeri olabilir. Ancak, {5, 1, 6, 3} bir alt dizi olamaz çünkü elemanlar ardışık bir sırada değildir.

Dikkat ederseniz, tüm alt diziler arasında, vurgulanan alt dizi {5, 1, 6} en yüksek toplam değere sahiptir:

{5, 1, 6} alt dizisinin toplamı 12'dir; bu, yukarıdaki dizinin tüm olası alt dizileri arasında elde edilebilecek maksimum toplamdır. Dolayısıyla, bu dizi için en yüksek toplamlı bitişik alt dizi {5, 1, 6}'dır.

En Büyük Toplamlı Bitişik Alt Dizi Problemini Çözmek İçin Basit Bir Yaklaşım

Bu sorunu çözmenin basit yolu, tüm alt dizileri bulmak için iki döngü kullanmak, toplamı hesaplamak ve ardından maksimum değerini bulmaktır.

İşte en büyük toplamlı bitişik alt diziyi bulmaya yönelik basit yaklaşımın akış şeması. Bu, her olası alt diziyi tek tek incelediğimiz kaba kuvvet yaklaşımıdır.

İşte bunu yapmanın basit adımları.

) 1 Adım başlat maksimum_toplam minimum tamsayı değeriyle ve ayarlanmış olarak başlamak hem de son sıfıra.

) 2 Adım Let i hem de j dizi indeksleri olsun j büyük veya eşit i; i alt dizinin başlangıcını işaretler ve j Sonu.

) 3 Adım mevcut_toplam Toplamı tutar. Her güncellemeden sonra kontrol edin. mevcut_toplam daha büyüktür maksimum_toplam.

) 4 Adım If mevcut_toplam daha büyükse, değiştirin maksimum_toplam onunla.

) 5 Adım Ne zaman j Dizinin sonuna ulaşıldığında, artırılır. i ve sıfırla mevcut_toplam 0 için.

) 6 Adım E kadar tekrar edin i Dizinin sonuna ulaşır. maksimum_toplam daha sonra en büyük alt dizi toplamını tutar.

Sözde Code Basit Yaklaşım için

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

C++ Basit Yaklaşımın Uygulanması

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

Çıktı:

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

Python Basit Yaklaşımın Uygulanması

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)

Çıktı:

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

En Büyük Toplama Sahip Bitişik Alt Diziyi Bulmak İçin Kadane Algoritması

Kadane algoritması, iki döngü yerine tek bir döngü kullanan dinamik programlama yöntemidir. En az bir değerin negatif olmaması koşuluyla, pozitif ve negatif sayıların karışık olduğu dizileri işleyebilir.

En büyük toplamlı bitişik alt diziyi bulmak için yalnızca iki değişkene ihtiyacımız var. İşte akış şeması:

İşte Kadane Algoritmasının adımları:

) 1 Adım İki değişken oluşturun, mevcut_toplam hem de maksimum_toplam.

mevcut_toplam Belirli bir dizi indeksinde sona eren maksimum toplamı korurken maksimum_toplam Şimdiye kadar gözlemlenen en büyük toplam değerini saklar.

) 2 Adım Dizideki her bir elemanı ekleyin. mevcut_toplamArdından aşağıdaki iki koşulu kontrol edin:

• If mevcut_toplam mevcut elemandan daha küçükse, o zaman mevcut_toplam Mevcut öğe haline gelir.
• If maksimum_toplam daha az mevcut_toplam, Daha sonra maksimum_toplam olur mevcut_toplam.

) 3 Adım Önceki adımı dizinin tamamı için tekrarladıktan sonra, maksimum_toplam En büyük toplam bitişik alt diziyi içerir.

Kadane Algoritması Örneği

Kadane algoritmasını küçük bir dizi üzerinde gösteriyoruz ve en büyük toplamlı bitişik alt diziyi bulmanın her adımını inceliyoruz.

Verilen dizinin aşağıdaki gibi olduğunu varsayalım:

Kadane algoritmasının adımları şunlardır:

) 1 Adım İki değişken oluşturun, mevcut_toplam hem de maksimum_toplamINT_MIN'i atayın maksimum_toplam ve sıfırdan mevcut_toplamBurada INT_MIN, en küçük tamsayı değerini temsil eder.

) 2 Adım 0 indeksinde değer 4'tür. Dolayısıyla, mevcut_toplam = 0 + 4 = 4. Çünkü mevcut_toplam daha büyüktür maksimum_toplam, maksimum_toplam 4 olur.

) 3 Adım 1. indekste değer -2'dir. Dolayısıyla, mevcut_toplam = 4 + (-2) = 2.

Bu kez mevcut_toplam daha az maksimum_toplamSonuç olarak, değeri maksimum_toplam güncellenmedi.

) 4 Adım Sonraki değer 1'dir. Bunu ekleyerek... mevcut_toplam 3 verir. Çünkü maksimum_toplam (4) hala daha büyüktür mevcut_toplam, maksimum_toplam güncellenmedi.

) 5 Adım 3. indekste değer 3'tür. Artış mevcut_toplam 3 ile çarpıldığında sonuç verir mevcut_toplam = 6.

Bu durumda, maksimum_toplam den daha küçük mevcut_toplam, yani maksimum_toplam değeriyle güncellenir. mevcut_toplam.

) 6 Adım Dizinin son elemanı -1'dir. Bunu ekleyerek... mevcut_toplam 5 verir, bu da daha küçüktür. maksimum_toplam. Yani, maksimum_toplam 6 kalır.

Dizinin sonuna ulaştığımız için algoritma burada sona eriyor. Şimdi, maksimum_toplam En büyük toplamı 6 olan alt dizi {4, -2, 1, 3}'tür.

Sözde Code Kadane'nin Algoritması için

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 Algoritmasının Uygulanması

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

Çıktı:

largest sum is 12

Python Kadane Algoritmasının Uygulanması

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

Çıktı:

largest sum is 12

En Büyük Toplam Bitişik Alt Dizi İçin Karmaşıklık Analizi

Basit yaklaşım, her olası alt dizi toplamını hesaplamak ve en büyüğünü bulmak için iki döngü kullanır. Bu, kaba kuvvet yaklaşımıdır; her döngü dizinin sonuna kadar çalışır. dizivererek O(N²) Zaman.

Kadane algoritması yalnızca tek bir döngü kullanır, bu da O(N) zaman karmaşıklığı ve O(1) ek alan sağlar. 100 elemanlı bir dizide basit yaklaşım 100 × 100 = 10,000 işlem gerçekleştirirken, Kadane algoritması yalnızca 100 işlem gerçekleştirir; bu da büyük girdiler için önemli bir hız artışı anlamına gelir.

SSS