Kadence Algoritması: En Büyük Toplamlı Bitişik Alt Dizi
Sarah Chen
En büyük toplam 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 bir dizi {-10, 5, 1, 6, -9, 2, -7, 3, -5}'tir. Alt dizileri şunlar olabilir: {-10,5,1,6} veya {5,1,6} veya {2,7,3, -5} vb. Ancak {5,1,6,3} bir olamaz alt dizi çünkü dizileri korumuyorlar.
Dikkat ederseniz, tüm alt diziler arasında, vurgulanan alt dizi (5,1,6) maksimum toplama değerine sahiptir:
{5,1,6} = 11 alt dizisinin toplamı, yukarıdaki dizinin tüm olası alt dizi kombinasyonlarındaki maksimum toplamdır. Yani yukarıdaki dizi için maksimum alt dizi {5,1,6}'tır.
Kadence Algoritması: En Büyük Toplamlı Bitişik Alt Dizi
En büyük toplam bitişik alt diziyi çözmeye basit 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.
En büyük toplam bitişik alt diziyi bulmaya yönelik basit yaklaşımın akış şemasını burada bulabilirsiniz. Olası tüm alt dizilerden geçtiğimiz için bu kaba kuvvet yaklaşımıdır.
İşte bunu yapmanın basit adımları.
) 1 Adım Max_sum'u minimum tamsayı değeriyle başlatın ve "begin" ve "end" değişkenlerine sıfırla atayın.
) 2 Adım i ve j dizinin indeksi olsun; burada "j" "i"den büyüktür. Alt dizinin başlangıç indeksini, “j” ise alt dizinin bitiş indeksini temsil eder.
) 3 Adım “Current_sum” alt dizinin toplamını tutacaktır. Geçerli toplamı hesapladıktan sonra, geçerli_toplamın maksimum_toplamdan büyük olup olmadığını kontrol edin.
) 4 Adım Geçerli_sum daha büyükse, max_sum'u geçerli toplamla değiştirin.
) 5 Adım “j”nin dizinin sonuna ulaşıp ulaşmadığını kontrol edin. Eğer “j” dizinin sonuna ulaşırsa, “i”yi artırın ve current_sum değerini 0 olarak değiştirin.
) 6 Adım Tüm bu adımları “i” dizinin sonuna ulaşana kadar gerçekleştirin.
) 7 Adım Bu iki döngünün sonunda max_sum en büyük alt dizi toplamını tutacaktır.
Basit yaklaşım için Sözde Kod
function maximumSubarraySum():
input: array
for all possible subArray from array:
calculate sum of each sub array
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 toplam bitişik alt diziyi bulmak için Kadane Algoritması
Kadane Algoritması bir tür “Dinamik Programlama” yöntemidir. Burada iki döngü yerine bir döngü kullanacağız. Kadane Algoritmasının genel uygulaması yalnızca pozitif sayı dizileri için işe yarar.
En büyük toplam bitişik alt diziyi bulmak için yalnızca iki değişkene ihtiyacımız var. İşte Kadane Algoritmasının akış şeması:
İşte Kadane Algoritmasının adımları:
) 1 Adım Current_sum ve max_sum olmak üzere iki değişken oluşturun.
"Current_sum" belirli bir dizi indeksinde biten maksimum toplamın değerini tutarken, "max_sum" o ana kadarki maksimum toplam değerini saklar.
) 2 Adım Her dizi öğesi için değeri current_sum ile ekleyeceğiz. Daha sonra aşağıdaki iki koşulu kontrol edeceğiz:
- current_sum geçerli öğeden küçükse, current_sum değeri geçerli öğe olacaktır.
- Maksimum_toplam geçerli_toplamdan küçükse, maksimum_toplam geçerli_toplam olacaktır.
) 3 Adım Önceki adımı tüm dizi için uygulayarak, "max_sum" değişkeninde en büyük toplam bitişik alt diziye sahip olacağız.
Kadane Algoritması Örneği
Kadanes Algoritmasını küçük boyutlu bir diziyle göstereceğiz ve en büyük toplam bitişik alt diziyi bulmanın her adımını tartışacağız.
Verilen dizinin aşağıdaki gibi olduğunu varsayalım:
İşte Kadane Algoritmasının adımları:
) 1 Adım Current_sum ve max_sum olmak üzere iki değişken oluşturun. INT_MIN'i max_sum'a, sıfırı da current_sum'a atayın. (Burada INT_MIN minimum tam sayı anlamına gelir).
) 2 Adım Dizin 0'da değer 4'tür. Yani, current_sum = 0 + 4 veya 4. Burada current_sum max_sum'dan daha büyüktür, max_sum 4 olacaktır.
) 3 Adım Dizin 1'de değer -2'dir. Yani, geçerli_toplam = 4 + (-2) veya 2.
Bu sefer current_sum max_sum'dan daha az. Sonuç olarak max_sum'un değeri güncellenmeyecektir.
) 4 Adım Bir sonraki değer 1'dir. Bunu geçerli_toplamla toplarsak, geçerli_toplam 3 olur. Yine de maksimum_toplam, geçerli_toplamdan büyüktür. Yani max_sum güncellenmeyecek.
) 5 Adım Dizin 3'te değer üçtür. Current_sum'u 3 artırarak değeri güncelleyeceğiz. Yani current_sum 6 olacaktır.
Bu durumda max_sum, current_sum'dan daha küçüktür. Böylece max_sum, current_sum değeriyle güncellenecektir.
) 6 Adım Dizinin son elemanı için -1'imiz var. Bunu current_sum ile eklersek, current_sum 5 olacaktır, bu da max_sum'dan küçük olacaktır. Yani max_sum 6 olarak kalacak.
Dizinin sonuna geldiğimizde algoritma burada bitiyor. Artık “max_sum” maksimum toplam alt dizisini içerir. Bu da 5'tir. Alt dizi {4,-2,1,3}'tir.
Kadane Algoritmasının Sahte Kodu
function KadaneAlgorithm():
input: array
maximum_sum, current_sum = 0
for each elements 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 -10000000
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 iki döngü kullanır. Bu yöntem, en büyüğünü bulmak için tüm olası alt dizi toplamlarını hesaplar. Bu kaba kuvvet yaklaşımıdır. Her döngü döngünün sonuna kadar devam eder dizi.
Bir dizinin toplamı varsa N elemanları, sonra iki döngü kullanarak N'den geçeceğiz2 öğeler. Sonuç olarak, en büyük toplam bitişik alt diziyi bulmak için basit bir yaklaşımın zaman karmaşıklığı şu şekilde olacaktır: O(N2). Burada “O” karmaşıklık fonksiyonunu ifade etmektedir.
Öte yandan Kadane Algoritması, maksimum bitişik toplam alt dizisini bulmaya yönelik Dinamik Programlama yöntemidir. Örneği veya kodu takip ederseniz yalnızca bir döngü kullandığımızı göreceksiniz.
Sonuç olarak, giriş dizisinin boyutu varsa N, o zaman Kadane Algoritmasının zaman karmaşıklığı O(N) olacaktır. Bu basit yaklaşımdan daha hızlıdır. Örneğin, 100 eleman içeren bir dizi. Basit yaklaşım 100*100 veya 10,000 CPU zamanı alacaktır. Ancak Kadane Algoritması yalnızca 100 CPU zamanı alacaktır.
