Maksimum Alt Dizi ve Maksimum Çarpımlı Alt Dizi
Maksimum toplamlı alt dizi için Kadane algoritmasını uygulayın ve çarpım varyantında hem maksimumu hem minimumu izlemek üzere genişletin.
Maksimum Alt Dizi ve Maksimum Çarpımlı Alt Dizi, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
Maksimum Toplamlı Alt Dizi Problemi
Maksimum Alt Dizi problemi, tek boyutlu bir sayı dizisi içindeki toplamı en büyük olan bitişik alt diziyi bulmanızı ister. Örneğin [-2, 1, -3, 4, -1, 2, 1, -5, 4] dizisinde [4, -1, 2, 1] alt dizisinin toplamı 6 ile en büyüktür. Kaba kuvvet kullanan O(n²) yaklaşımı tüm alt dizileri denetler, ancak Kadane algoritması bu problemi O(n) içinde çözer.
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Brute force: O(n^2)
max_sum = float('-inf')
for i in range(len(nums)):
curr = 0
for j in range(i, len(nums)):
curr += nums[j]
max_sum = max(max_sum, curr)
print(max_sum) # 6Kadane Algoritmasının Sezgisi
Kadane algoritması, dizi boyunca tek geçiş yaparken biriken current_sum değerini tutar. Her öğede şu kararı verirsiniz: mevcut alt diziyi genişletmek mi, yoksa bu öğeden yeni bir alt dizi başlatmak mı daha iyi? current_sum negatif olursa gelecekteki her alt diziye yalnızca zarar vereceğinden yeniden başlatılır. Bağıntı şöyledir: current_sum = max(num, current_sum + num).
def max_subarray(nums):
max_sum = current_sum = nums[0]
for num in nums[1:]:
# Extend or start fresh?
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(nums)) # 6Kadane Algoritmasını İzleme
[-2, 1, -3, 4, -1, 2, 1, -5, 4] üzerinde Kadane algoritmasını izleyelim: curr=-2, max=-2 ile başlayın. 1 için: curr=max(1,-2+1)=1, max=1. -3 için: curr=max(-3,1-3)=-2, max=1. 4 için: curr=max(4,-2+4)=4, max=4. -1 için: curr=3, max=4. 2 için: curr=5, max=5. 1 için: curr=6, max=6. -5 için: curr=1. 4 için: curr=5, max=6. Algoritma, 6. indiste sona eren alt dizinin en iyi seçenek olduğunu doğru biçimde belirler.
def max_subarray_trace(nums):
curr = max_sum = nums[0]
for i, num in enumerate(nums[1:], 1):
new_curr = max(num, curr + num)
max_sum = max(max_sum, new_curr)
print(f'i={i}, num={num}, curr: {curr}->{new_curr}, max={max_sum}')
curr = new_curr
return max_sum
max_subarray_trace([-2, 1, -3, 4, -1, 2, 1, -5, 4])Gerçek Alt Diziyi Döndürme
Mülakatı yapan kişi sizden yalnızca toplamı değil, alt dizinin kendisini döndürmenizi isterse başlangıç ve bitiş indislerini takip etmeniz gerekir. Yeniden başlattığınızda (num > current_sum + num nedeniyle) bir temp_start güncelleyin. max_sum değerini güncellediğinizde temp_start değerini start olarak ve geçerli indisi end olarak kaydedin. Bu, aynı O(n) algoritmasına O(1) ek maliyet getirir.
def max_subarray_indices(nums):
max_sum = curr = nums[0]
start = end = temp_start = 0
for i in range(1, len(nums)):
if nums[i] > curr + nums[i]:
curr = nums[i]
temp_start = i
else:
curr += nums[i]
if curr > max_sum:
max_sum = curr
start, end = temp_start, i
return max_sum, nums[start:end+1]
print(max_subarray_indices([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# (6, [4, -1, 2, 1])Maksimum Çarpımlı Alt Dizi Problemi
Maksimum Çarpım Alt Dizisi problemi, negatif sayılar nedeniyle toplam çeşidinden daha zordur. İki negatif sayının çarpımı pozitif olur; bu nedenle çok negatif bir çarpım, başka bir negatif sayıyla çarpıldığında maksimuma dönüşebilir. [2, 3, -2, 4] için cevap 6'dır ([2, 3]). [-2, 0, -1] için cevap 0'dır. Her adımda hem maksimum hem de minimum çarpımları takip etmeliyiz.
nums = [2, 3, -2, 4]
# [2,3,-2,4]: products [2, 6, -12, -48]
# subarrays: [2]=2, [2,3]=6, [3]=3, etc.
# max is 6 from subarray [2,3]
nums2 = [-2, 3, -4]
# [-2]*3*[-4] = 24
# negative*negative=positive!
print('Expected:', 24)Maksimum ve Minimum Çarpımların İkisini de Takip Etme
Temel fikir şudur: Her konumda geçerli maksimum çarpım num, max_so_far * num veya min_so_far * num değerlerinden biridir (negatif bir sayı minimumu maksimuma çevirdiğinde sonuncusu yardımcı olur). Minimum için de benzer bir işlem yapılır. Aynı adımda zaten güncellenmiş değerleri kullanmamak için önceki değerleri kullanarak hem cur_max hem de cur_min değerlerini eşzamanlı olarak güncelleyin.
def max_product(nums):
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
# All three candidates for new max
candidates = (num, max_prod * num, min_prod * num)
max_prod, min_prod = max(candidates), min(candidates)
result = max(result, max_prod)
return result
print(max_product([2, 3, -2, 4])) # 6
print(max_product([-2, 3, -4])) # 24
print(max_product([-2, 0, -1])) # 0
print(max_product([-2])) # -2min_prod Neden Önemlidir
[-3, -10, 5] dizisini düşünün. -3 işlendiğinde: max=-3, min=-3. -10'dan sonra adaylar (-10, 30, 30) → max=30, min=-10 olur. 5'ten sonra adaylar (5, 150, -50) → max=150 olur. min_prod değerini takip etmezseniz, büyük negatif bir minimum başka bir negatifle çarpıldığında gerçekleşen dönüşümü kaçırırsınız. Eski bir okuma hatasını önlemek için max ve min değerlerini her zaman aynı önceki değerlerden hesaplayın.
def max_product_traced(nums):
max_p = min_p = result = nums[0]
for num in nums[1:]:
prev_max, prev_min = max_p, min_p
max_p = max(num, prev_max * num, prev_min * num)
min_p = min(num, prev_max * num, prev_min * num)
result = max(result, max_p)
print(f'num={num}: max_p={max_p}, min_p={min_p}')
return result
max_product_traced([-3, -10, 5])
# max_p after -10: 30 (flip!)
# max_p after 5: 150Sıfırlar Çarpımı Sıfırlar
Dizideki bir sıfır, her iki birikimli çarpımı da sıfırlayarak diziyi bağımsız alt dizilere ayırır. num = 0 olduğunda hem max_prod * 0 = 0 hem de min_prod * 0 = 0 olur; böylece üç adayın tümü 0'a dönüşür ve önceki sonucun maksimumu korunur. Özel durum kodu yazmanız gerekmez — genel formül sıfırları doğal biçimde ele alır.
def max_product(nums):
max_p = min_p = result = nums[0]
for num in nums[1:]:
cands = (num, max_p * num, min_p * num)
max_p, min_p = max(cands), min(cands)
result = max(result, max_p)
return result
# Zero splits array into independent subarrays
print(max_product([3, -1, 4, 0, 2, 5, -1])) # 10 (2*5)
print(max_product([0, 2])) # 2
print(max_product([-1, 0, -2])) # 0Soldan Sağa Ürün Taraması Alternatifi
Alternatif bir yaklaşım soldan sağa ve sağdan sola tarama yapar; sıfıra ulaştığında birikimli çarpımı 1'e sıfırlar. Maksimum çarpımlı alt dizi hiçbir zaman bir sıfırı aşmaz. Bu nedenle negatif bir sayı bir yönde sonucu kötüleştirirse ters yöndeki tarama dönüşümü yakalar. Bu yaklaşım zariftir, ancak minimum/maksimum takibi yöntemi mülakatlarda daha sık beklenir.
def max_product_sweep(nums):
result = max(nums)
left = right = 1
n = len(nums)
for i in range(n):
left *= nums[i]
right *= nums[n - 1 - i]
result = max(result, left, right)
if left == 0: left = 1
if right == 0: right = 1
return result
print(max_product_sweep([2, 3, -2, 4])) # 6
print(max_product_sweep([-2, 3, -4])) # 24
print(max_product_sweep([-2, 0, -1])) # 0Kadane ve Çarpım: Temel Farklar
Toplam ve çarpım alt dizileri önemli açılardan farklıdır. Toplamda negatifler her zaman zararlıdır; bu nedenle açgözlü biçimde yeniden başlatırsınız. Çarpımda ise iki negatif sayı faydalı olabilir; bu yüzden her iki uç değeri de takip etmeniz gerekir. Ayrıca sıfırlar çarpımlar için sonlandırıcıdır, ancak toplamlar için yalnızca hafifçe zararlıdır. Mülakatlarda bu farkları açıkça belirtin ve herhangi bir kod yazmadan önce minimumu takip etmenin neden gerekli olduğunu açıklayın.
# Max Sum Subarray: O(n) time, O(1) space
def max_sum(nums):
curr = result = nums[0]
for n in nums[1:]:
curr = max(n, curr + n) # restart or extend
result = max(result, curr)
return result
# Max Product Subarray: O(n) time, O(1) space
def max_prod(nums):
lo = hi = result = nums[0]
for n in nums[1:]:
lo, hi = min(n, lo*n, hi*n), max(n, lo*n, hi*n)
result = max(result, hi)
return result
print(max_sum([-2, 1, -3, 4, -1, 2, 1])) # 6
print(max_prod([-2, 3, -4])) # 24Karmaşıklık ve Mülakat İpuçları
Hem Kadane algoritması (maksimum toplam) hem de minimum/maksimum takibi (maksimum çarpım) O(n) zamanda ve O(1) alanda çalışır. Mülakat için temel ipuçları: (1) Maksimum toplam için kapsamınızı göstermek amacıyla Böl ve Yönet yaklaşımının O(n log n) alternatifinden bahsedin. (2) Maksimum çarpım için, eski verileri kullanmaktan kaçınmak üzere min_prod ve max_prod değerlerini önceki değerlerden eşzamanlı olarak güncellediğinizi vurgulayın. (3) Her zaman şu noktaları netleştirin: Dizi boş olabilir mi? Alt dizi boş olamaz mı? (Evet, geleneksel olarak boş olmamalıdır.)
# Both run O(n) time, O(1) space
# Kadane handles: all negative (returns least negative)
# Product handles: zeros (resets naturally), negatives (tracks both extremes)
nums_all_neg = [-5, -2, -8]
print('Max sum (all neg):', max(max(nums_all_neg[0:1]),
max(x for x in nums_all_neg))) # -2
# Correct: return the maximum element when all are negativeKısa Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını ne ölçüde anladığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: Kadane algoritması, her öğede genişletmeyi veya yeniden başlatmayı seçerek maksimum toplamlı alt diziyi O(n) içinde çözer, negatif sayıların yön değiştiren etkileri nedeniyle maksimum çarpımlı alt dizi hem minimum hem de maksimum birikimli çarpımların takip edilmesini gerektirir ve sıfırlar, özel durum kodu gerektirmeden birikimli çarpımı doğal olarak sıfırlar. Sırada, tek boyutlu bir DP tablosu kullanarak Kelimeleri Ayırma problemini inceleyeceğiz.
Sıkça Sorulan Sorular
“Maksimum Alt Dizi ve Maksimum Çarpımlı Alt Dizi” dersi ücretsiz mi?
Evet — “Maksimum Alt Dizi ve Maksimum Çarpımlı Alt Dizi” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“Maksimum Alt Dizi ve Maksimum Çarpımlı Alt Dizi” dersinde ne öğreneceğim?
Maksimum toplamlı alt dizi için Kadane algoritmasını uygulayın ve çarpım varyantında hem maksimumu hem minimumu izlemek üzere genişletin. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“Maksimum Alt Dizi ve Maksimum Çarpımlı Alt Dizi” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Ev Soyguncusu: Al veya Atla Bağıntısı
- Maksimum Alt Dizi ve Maksimum Çarpımlı Alt Dizi
- Sözcük Bölme ve Dizeyi Parçalara Ayırma
- Yolları Çözümleme ve Yolları Sayma