Kadane Algoritması
Dinamik Programlama O(n) O(1)Tek geçişte maksimum alt dizi toplamı: süregelen toplam yardım ettikçe uzat, negatife dönünce mevcut elemandan yeniden başla.
1/22
Başlangıç: best = cur = a[0] = -2.
Değişmezcur, tam olarak i'de biten bir dizinin en büyük toplamıdır; best ise her yerde görülen en büyüğüdür.
kadane.c
int kadane(int a[], int n) {int best = a[0];int cur = a[0];for (int i = 1; i < n; i++) {if (cur + a[i] > a[i])cur = cur + a[i]; /* extend the run */elsecur = a[i]; /* restart run here */if (cur > best)best = cur;}return best;}
Kadane Algoritması nasıl çalışır?
Diziyi tek geçişte yürü ve burada biten en iyi toplamı tut: ya süregelen toplamı uzat ya da toplam negatife düştüyse mevcut elemandan yeniden başla — negatif önek asla yardım edemez.
En iyi durum
Her zaman tek geçiş: O(n), O(1) alan.
En kötü durum
Tamamı negatif diziler de çalışır — yanıt en büyük tek elemandır.
Ne zaman kullanılır?
Maksimum alt dizi toplamı: en iyi alım-satım penceresi, en parlak görüntü şeridi, 1B kâr aralıkları.