Kadane algoritması nedir? Maksimum toplamlı alt diziyi (Maximum Subarray) bulun.

Kadane algoritması, her indekste o indekste biten en iyi alt dizi toplamını tutar: ya önceki alt diziye eklenir ya da yeni bir alt dizi başlatılır. O(n) zaman ve O(1) bellekte çalışır.

cur = max(x, cur + x): önceki toplam negatifse onu taşımak zarar verir, sıfırdan başlamak daha iyidir.

def max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6  -> [4, -1, 2, 1]
print(max_subarray([-3, -1, -2]))                     # -1 (tümü negatif)

Adım adım

Tuzaklar

• best = 0 ile başlamak, tüm elemanlar negatifken yanlış sonuç (0) verir. İlk elemanla başlayın.
• Alt dizinin başlangıç ve bitiş indeksi istenirse cur sıfırlandığında geçici başlangıcı kaydedin.

Neden bir DP?

dp[i] = max(nums[i], dp[i-1] + nums[i]) geçişidir; yalnızca bir önceki değer kullanıldığı için dizi yerine tek değişken yeterlidir.

İlgili sorular: Maximum Product Subarray (hem min hem max tutulur, çünkü negatif x negatif pozitiftir), Best Time to Buy and Sell Stock.