CP #6 : Maximum Subarray Problemi
Problem surada.
Cozum
Yine naive implementasyon ile baslayabiliriz. Benim ilk aklima gelen bir tabulasyon olusturmak ve tum start-end komninasyonlarini burada tutmakti.
maks = float("-Infinity")
cache = [[0]*len(nums) for t in range(len(nums))]
# 1 uzunluktaki sub-arraylar
for i in range(len(nums)):
cache[i][i] = nums[i]
# 2 uzunluktasi sub-arrayler
for i in range(1, len(nums)-1):
cache[i][i+1] = cache[i][i] + nums[i+1]
# 3 uzunluktaki sub-arrayler
for i in range(2, len(nums)-2):
cache[i][i+2] = cache[i][i+1] + nums[i+2]
Kodu yazarken bile brute-force kullandik :D Burada olusan pattern'i gormus olduk. Simdi bunu daha dinamik sekilde yazarsak:
class Solution:
def maxSubArray(self, nums):
maks = float("-Infinity")
cache = [[0]*len(nums) for t in range(len(nums))]
for k in range(len(nums)):
for i in range(len(nums)-k):
cache[i][i+k] = cache[i][i+k-1] + nums[i+k]
maks = max(maks, cache[i][i+k])
return maks
Ama malesef burada iki dongu kullandigimiz icin O(n^2) cozum leetcode'da timeout oluyor. Nasil optimize edebiliriz?
Optimizasyon
Diyelim ki makx sub-arrayi olusturuyoruz. Bir yerden basladik. Peki siradaki gelen item'i dahil etmeli miyiz etmemeli miyiz?
Ornegin, [-2,1,-3,4,-1,2,1,-5,4] dizesini ele alalim.
Diyelim -2'den basladik.
Daha sonra gelecek 1'i mevcut sub-array'e (-2'den baslatmistik) dahil etmeli miyiz?
Yoksa direk olarak 1'den baslasak daha mi avantajli oluruz?
Elbette ki 1'den baslamak daha avantajli.
O zaman sunu diyebiliriz, eger karsilastigimiz elemani elimizdeki mevcut sub-arraye dahil ettigimizde elde ettigimiz toplam elemanin kendisinden kucuk ise bu direk bu elemandan dizeye baslamak daha avantajlidir.
Baska bir degisle, egere bu elemandan onceki toplam bu eleman ile birlestiginde ortalam dusuyorsa, direk bu elemandan basladigimizda bile daha buyuk bir toplama ulasiri.
Ornegin [-3, -4, 1] buradaki maksimum sub-array [1] dir.
Ikinci secenek ise, bu elemani mevcut toplama ekledigimizde, toplam, elemanin kendisinden daha buyuk oluyor. Yani biz direk bu elemandan baslarsak daha dezavantajli oluyoruz. Bu durumda o elemani diziye dahil etmemiz gerekir.
Ornegin [4, -1, 2] dizesinde 4'ten basladi ise, -1'i dahil etmeli miyiz? Evet, cunku egere direk -1'den baslarsak toplam -1 olacak, ama oysa ki eldeki dizeye dahil edersek toplam 3 olur. Daha avantajli.
Bunu soylerken de bir ust cumlede sunu farkediyoruz, -1'i hic almasak daha iyi degil mi? 4 zaten daha buyuk. Dogru. Aslinda burada iki farkli toplam degeri track ediyoruz. Birincisi global maximum. Ki bu da ornekte 4 aslinda. Her adimda, elde ettigimiz local maximum'u global maximum ile kiyaslayip, global maximumu guncelliyoruz.
Cok da uzatmadan, final haline bir goz atalim:
class Solution:
def maxSubArray(self, nums):
global_maks = float("-Infinity")
lokal_mak = 0
for i in range(len(nums)):
if lokal_maks + nums[i] < nums[i]:
lokal_maks = nums[i]
else:
lokal_maks += nums[i]
global_maks = max(global_maks, lokal_maks)
return global_maks
Ilk basta global mak olarak -sonusz degerini atiyoruz ki, ilk elde edecegimiz negatif bir sonuc dahi global maks'in yerine gecebilsin. Sonucta tamami negati sayilardan olusan bir sub-array de mumkun.
Daha sonra gelen elemani bahsettigimiz gibi kontrol ediyoruz.
Eger direk bu elemandan baslamak oncekilerden daha avantajli ise, aslinda baslangic noktasi olarak bu noktayi aliyoruz. Eger degilse de lokal_sum'a eklemeye devam ediyoruz.
Bu sayede ki, [-2,1,-3,4,-1,2,1,-5,4] dizesinde 4'ten basliyoruz. Daha sonra -1'i de dahil ediyoruz cunku direk -1'den baslasak daha kotu olacak. Daha sonra 2'yi de dahil ediyoruz. Cunku yine 2'den baslamak daha kotu. Baslangic noktasini sabitledikten sonra, arrayin sonuna kadar gidebiliyoruz. Cunku zaten her item'de global max'i guncelliyoruz.
Analiz
Diziyi sadece bir kere traverse ettigimize gore O(n) kompleksiteye sahibiz demektir. Hafiza gereksinimi de sadece lokal_maks ve global_maks degiskenleridir ki bu da constant time demek, O(1).
Gorusmek uzere.
Yorumlar
Yorum Gönder