Kadane Algoritması

Kadane Algoritması, belirli bir sayı dizisi içindeki maksimum alt dizi toplamını bulmak için kullanılan dinamik bir programlama tekniğidir. Dinamik Programlama, karmaşık bir problemi daha basit alt problemlerden oluşan bir koleksiyona bölerek, bu alt problemlerin her birini yalnızca bir kez çözerek ve çözümlerini bellek tabanlı bir veri yapısı (dizi, harita vb.) kullanarak saklayarak çözme yöntemidir. Yani bir dahaki sefere aynı alt problem ortaya çıktığında, çözümünü yeniden hesaplamak yerine, daha önce hesaplanan çözüme bakılır ve böylece hesaplama süresinden tasarruf edilir. Adını mucidi Jay Kadane'den alan algoritma; bilgisayar bilimi ve veri analizinden finans ve görüntü işlemeye kadar çeşitli alanlarda uygulamalara sahiptir. Algoritma 1984 yılında Jay Kadane tarafından önerilmiştir ve O(n) zaman karmaşıklığına sahiptir. 

Kadane Algoritması, belirli bir dizideki maksimum alt dizi toplamını bulmak için kullanılan doğrusal bir zaman algoritmasıdır. Bir alt dizi, dizi içindeki öğelerin bitişik bir alt kümesi olarak tanımlanır. Algoritma, pozitif ve negatif sayıları çok verimli bir şekilde ele alır, bu da onu alt dizileri içeren birçok sorunu çözmek yerine daha pratik çok yönlü bir çözüm aracı haline getirir.Kadane'nin algoritmasından önce, maksimum alt dizi problemini çözmek için tüm olası alt dizileri kontrol eden kaba kuvvet yaklaşımı ve böl ve yönet algoritması gibi başka algoritmalar önerilmişti. Ancak bu algoritmalar daha yüksek zaman karmaşıklığına sahiptir ve Kadane'nin algoritmasından daha az verimlidir. Kadane'nin Algoritmasının altında yatan mekanizmaları, Java kodu uygulamalarını, adım adım süreci, Kadane'nin algoritma leetcode'unu, C, C++'yi, zaman karmaşıklığını, avantajlarını ve dezavantajlarını, pratik uygulamaları ve daha fazlasını anlamanız sizin için faydalı olacaktır.

Kadane Algoritması, dizi üzerinde yineleme yaparak ve her konumda biten alt dizinin maksimum toplamını takip ederek çalışır. Her i konumunda, iki seçeneğimiz vardır: ya i konumundaki elemanı geçerli maksimum alt diziye ekleyin ya da i konumunda yeni bir alt dizi başlatın. Bu iki seçeneğin maksimumu i konumunda biten maksimum altdizidir.

Yazılım dilinde bu algoritma şu şekilde işler: Başlangıç toplamı max_so_far ve max_ending_here değerleri 0 olarak alınıp dizi öğeleri tek tek incelenir. Sırasıyla şu ana kadar görülen maksimum toplamı ve geçerli konumda biten maksimum toplamı takip etmek için max_so_far ve max_ending_here olmak üzere iki değişkeni her dizi elemanında korunur. Algoritma, her iki değişkeni de dizinin ilk öğesinden başlayarak sırasıyla değiştirir. Daha sonra dizinin elemanlarını aldıktan sonra geçerli toplamı maksimum toplamla kıyaslayarak ikinci öğeden dizinin sonuna kadar aynı işlemler tekrarlanır. Her i konumunda, geçerli öğenin maksimumunu ve önceki maksimum alt diziye eklenen geçerli öğeyi alarak max_ending_here'i güncellenir. Daha sonra max_so_far'ı max_so_far ve max_ending_here'nin maksimumu olacak şekilde güncelleme işlemine devam edilir. Geçerli toplam maksimum toplamdan büyük ise artık yeni maksimum toplam değeri buna göre güncellenir aksi halde önceki maksimum toplam aynı kalır. Algoritma, dizideki herhangi bir alt dizinin maksimum toplamı olan max_so_far değerini sürekli olarak döndürür. Dizinin son terimine gelince işlem biter ve maksimum toplamı veren alt dizi elde edilir.

Kadane Algoritmasını şöyle bir sayı dizisi örneğiyle gösterelim:

Giriş Dizisi: [-2, 1, 6, -3, 4, -1, -7, -3, 5] Bu dizinin maksimum altdizi toplamını bulmak istiyoruz. Bu sorunu çözmek için Kadane'nin algoritmasını uygulayabiliriz.

İki değişkeni başlatarak algoritmayı başlatıyoruz:

1) max_so_far: Bu değişken şu ana kadar gördüğümüz maksimum alt dizi toplamını takip edecektir. (Geçerli Toplam)

2) max_ending_here: Bu değişken mevcut endekste biten maksimum toplamı takip edecektir. (Max Toplam)

3) İlk başlangıç toplamı max_so_far ve  max_ending_here=0 olur. Daha sonra ikinci elemandan başlayarak dizi boyunca toplamları yineliyoruz: Öğe -2 ye gidip yeni toplam -2 olur. (0+(-2)=-2) [Sub:-2]

4) Geçerli öğeyi önceki toplama ekleyerek geçerli toplamı güncelleyin: Geçerli Toplam=0+(-2)=-2 [Sub:-2]

5) Şu ana kadar görülen maksimum toplamı güncelleyin: 0+(-2)=-2 olur.(Maksimum Toplam=-2) [Sub:-2, Max:-2]

6) Dizi boyunca ilerleyerek yerel toplam (Geçerli toplam) ve maksimum toplam sonuçlarını yinelemeye başlayalım.

Dizide öğe 1 elemanına gelince: Geçerli toplam -1 olur. (-2+1=-1)  [Sub:-1]

Maksimum toplam, geçerli toplam olan -1, max toplam -2 yi geçtiği için -1 olarak güncellenir. [Sub:-1, Max:-1]

7) Öğe 6 elemanına gidelim: Yeni geçerli toplamı 5 olur. ((-1)+6=5) Maksimum toplamı ise 5 toplamı önceki maksimum toplam olan -1 sayısını geçtiği için güncellenir ve maksimum toplam 5 olur.  [Sub:5, Max:5]

8) Öğe -3'e gelince:Yeni geçerli toplamı 2 olur. (5+(-3)=2) Maksimum toplamı ise 2 toplamı önceki maksimum toplam olan 5 sayısını  sayısını geçemediği için aynı kalır. Yeni maksimum toplam halen 5'tir. [Sub:2, Max:5]

9)Öğe 4'e gelince:Yeni geçerli toplamı 6 olur. (2+4=6) Maksimum toplamı 6 ise önceki max toplam 5'i geçtiği için yeniden güncellenir ve yeni maksimum toplam 6 olur. [Sub:6, Max:6]

10)Öğe -1'e gelince:Yeni geçerli toplamı 5 olur. (6+(-1)=5) Maksimum toplamı ise 5 toplamı önceki maksimum toplam olan 6 sayısını geçemediği için halen aynı kalır ve 6 olur. [Sub:5, Max:6]

11)Öğe -7'e gelince:Yeni geçerli toplamı -6 olur. (5+(-7)=-2) Maksimum toplamı ise -2 önceki maksimum toplam olan 6 sayısını geçemediği için aynı kalır. [Sub:-2, Max:6]

12)Öğe -3'e gelince:Yeni geçerli toplamı -5 olur. ((-2)+(-3)=-5) Maksimum toplamı ise -5 önceki maksimum toplam olan 6 sayısını geçemediği için aynı kalır. [Sub:-5, Max:6]

13)Öğe 5'e gelince:Yeni geçerli toplamı 0 olur. ((-5)+5=0) Maksimum toplamı ise 0 toplamı önceki maksimum toplam olan 6 sayısını artık geçemediği için aynı kalır. [Sub:0, Max:6]

Tüm dizi için bu işleme devam edip en son öğeye gelidiği için işlem biter. Bu örnekteki maksimum alt dizi, toplamının en büyük olduğu değer 6 olduğundan buna uygun bir alt dizi [-2, 1, 6, -3, 4] olur.

Java ve C++ programlamada Kadane Algoritması şöyle çalışır:

1)İki değişkeni, max_so_far ve max_ending_here'i 0'a başlatın.

2)Diziyi soldan sağa doğru yineleyin ve her öğeyi tek tek inceleyin.

3)Her öğe için, maksimum değer ya geçerli öğe ya da geçerli öğe ile max_ending_here'in toplamı olduğundan max_ending_here'i güncelleyin.

4)Max_so_far'ı mevcut max_so_far veya max_ending_here'in maksimumu kadar güncelleyin.

5)Dizideki tüm öğeler için 3. ve 4. adımları tekrarlayın.

6)Yinelemenin sonundaki max_so_far değeri maksimum altdizi toplamı olacaktır.

#include <iostream>

using namespace std;

int maxSubarraySum(int arr[], int size) {

  int maxEndingHere = arr[0];

  int maxSoFar = arr[0];

  for (int i = 1; i < size; i++) {

      maxEndingHere = max(arr[i], maxEndingHere + arr[i]);

      maxSoFar = max(maxSoFar, maxEndingHere);

  }

  return maxSoFar;

}

int main() {

  int nums[] = {-2, -1, -3, 4, -1, 2, 1, -5, 4};

  int size = sizeof(nums) / sizeof(nums[0]);

  int maxSum = maxSubarraySum(nums, size);

  cout << "Maximum subarray sum: " << maxSum << endl;

  return 0;

}

Kaynakça:

https://www.tpointtech.com/kadanes-algorithm

https://www.simplilearn.com/kadanes-algorithm-article

https://www.interviewbit.com/blog/maximum-subarray-sum/

https://www.guru99.com/tr/largest-sum-contiguous-subarray.html

https://www.codecademy.com/resources/docs/general/algorithm/kadanes-algorithm