 Bir tamsayı dizisi verildiğinde, dizinin herhangi bir bitişik alt dizisinin maksimum toplamını bulun. Örneğin, giriş dizisi [-2,1,-3,4,-1,2,1,-5,4] ise, çıkış 6 olmalıdır (bitişik alt dizi [4,-1,2, 1]).
Bu soruna bir çözüm, maksimum alt dizi toplamını verimli bir şekilde bulmak için özel olarak tasarlanmış olan Kadane'nin algoritmasını kullanmaktır. İşte böyle çalışır: 1. Dizinin ilk öğesine iki değişken, maxSoFar ve maxEndingHere başlatın. 2. MaxEndingHere'i aşağıdaki gibi güncelleyerek dizinin geri kalanında döngü yapın: - maxEndingHere = max(nums[i], maxEndingHere + nums[i]) 3. Her yinelemede, maxSoFar'ı maxSoFar ve maxEndingHere'in maksimumu olacak şekilde güncelleyin. 4. Döngüden sonra maxSoFar'ı döndürün. İşte bu algoritmayı uygulayan Python kodu: ``` def maxSubarraySum(nums): maxSoFar = maxEndingHere = nums[0] for i in range(1, len(nums))): maxEndingHere = max(nums[i], maxEndingHere + nums[i]) maxSoFar = max(maxSoFar, maxEndingHere) return maxSoFar ``` Verilen [-2,1,-3,4,-1,2,1,-5,4] girişi için, bu fonksiyon şunu döndürür: 6, beklendiği gibi.