Maximum Subarray
Bir tamsayı listesi nums alıyorsun. Alt dizi, aralarında boşluk olmadan alınan bitişik elemanlardan oluşur ve en az bir eleman içermelidir. nums içindeki herhangi bir alt dizinin sahip olabileceği en büyük toplamı döndür. Yalnızca toplamı döndür, alt dizinin kendisini değil.
Fonksiyon
- numsinteger-array
- en az bir öğe içeren tam sayı listesi
- Döndürürinteger
- boş olmayan bitişik öğeler dizisinin en büyük toplamı
Kısıtlar
1 ≤ nums.length ≤ 105-104 ≤ nums[i] ≤ 104- Yanıt her zaman 32 bitlik işaretli bir tamsayıya sığar.
Örnekler
- Girdi
- nums = [2, -4, 3, -1, 5, -6, 1]
- Çıktı
- 7
- Açıklama
[3, -1, 5]dizisinin toplamı 7'dir. Sola doğru genişletmek önce -4, ardından 2 ekler; net kayıp 2 olur. Sağa doğru genişletmek önce -6, ardından 1 ekler; net kayıp 5 olur. Başka hiçbir dizi daha iyi sonuç vermez.
- Girdi
- nums = [-3, -1, -2]
- Çıktı
- -1
- Açıklama
- Tüm sayılar negatiftir, bu yüzden daha uzun bir dizi toplamı yalnızca düşürür ve en iyi dizi tek elemanlı -1 dizisidir. Alt dizi boş olamaz, bu nedenle yanıt 0 değil, -1'dir.
Ek soru
Bunu, listeyi ikiye bölüp ortayı aşan serileri ele alarak O(n log n) zaman karmaşıklığıyla böl ve fethet yöntemiyle de çözebilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Tam olarak bir konumda sona eren serilere odaklanın. Burada sona eren en iyi seri, hemen önceki konumda sona eren en iyi seriyle nasıl ilişkilidir?
Geçerli öğede sona eren bir dizi, ya hemen öncesinde sona eren diziyi sürdürür ya da bu öğede yeni baştan başlar. Devam etmek, yalnızca önceki dizinin toplamı pozitif olduğunda işe yarar.
Listeyi bir kez dolaş ve iki sayı tut: mevcut öğede sona eren bir dizinin en iyi toplamı ve şimdiye kadar görülen en iyi toplam. Her ikisini de ilk öğeyle başlat; böylece yalnızca negatif sayılardan oluşan bir liste yine de en büyük öğesini döndürür.
Çözüm
n sayıdan oluşan bir listenin yaklaşık n²/2 alt dizisi vardır; 10^5 eleman için bunları tek tek kontrol etmek çok fazladır. Zor olan negatif sayılardır: sonrasında gelenler bunu telafi ediyorsa bir dizi negatif elemanı tutmalı, etmiyorsa ondan önceki her şeyi atmalıdır. Kadane algoritması, her elemanda tek bir karşılaştırmayla bu seçimi yapar.
Her alt diziyi topla
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her alt dizinin bir ilk indeksi left ve bir son indeksi right vardır; bu nedenle her ikiliyi denemek en iyisini bulur. left değerini sabitle ve right değerini ilerletirken her yeni öğeyi biriken total değerine ekle: her alt dizi bir toplama işlemine mal olur ve üçüncü bir döngüye gerek kalmaz.
Yine de geriye yaklaşık n²/2 ikili kalır; 10^5 öğe için beş milyar toplama işlemi.
Algoritma
bestdeğerini ilk elemana ayarla.- Her
leftbaşlangıç indeksi için, birikentotaldeğerini 0 olarak ayarla. rightdeğerinileftkonumundan listenin sonuna kadar ilerlet venums[right]değerinitotaldeğerine ekle.- Her eklemeden sonra, daha büyükse
totaldeğerinibestiçinde sakla. bestdeğerini döndür.
def maxSubArray(nums):
best = nums[0]
for left in range(len(nums)):
total = 0
# Grow the subarray that starts at left by one element at a time
for right in range(left, len(nums)):
total += nums[right]
best = max(best, total)
return bestKadane algoritması
Sezgi
i indeksinde biten en iyi dizi ya yalnızca nums[i] değerinden ya da nums[i] eklenmiş, i-1 indeksinde biten en iyi diziden oluşur; çünkü i-1 indeksinde biten başka hiçbir dizinin toplamı daha büyük değildir. Bu yüzden mevcut öğede biten bir dizinin en iyi toplamı olan endingHere değerini tut. Sonraki öğe x olduğunda bu değer, x ile endingHere + x değerlerinden büyük olanına dönüşür: dizinin toplamı pozitif olduğu sürece onu genişletirsin, toplam sıfır veya negatif olduğundaysa x ile baştan başlarsın.
En iyi alt dizi bir yerde biter; dolayısıyla yanıt, endingHere değerinin aldığı en büyük değerdir. İlk örnekte değerler sırasıyla 2, -2, 3, 2, 7, 1, 2 olur ve yanıt 7'dir.
Algoritma
endingHerevebestdeğerlerini ilk elemana ayarla.- Sonraki her
xelemanı içinendingHeredeğerinixileendingHere + xdeğerlerinden büyük olana ayarla. bestdeğerinibestileendingHeredeğerlerinden büyük olana ayarla.- Son elemandan sonra
bestdeğerini döndür.
def maxSubArray(nums):
current = nums[0]
best = nums[0]
for i in range(1, len(nums)):
current = max(nums[i], current + nums[i])
best = max(best, current)
return best
Tuzaklar ve uç durumlar
bestdeğerini 0'dan başlatmak.[-3, -1, -2]bu durumda -1 yerine 0 döndürür. İlk elemandan başla.- Çalışan toplamı
max(0, endingHere + x)ile 0'a sabitlemek. Aynı listede başarısız olur; bunun yerinexile karşılaştır. - Yalnızca pozitif sayıları toplamak. Elemanların komşu olması gerekir; bu nedenle ilk örneğin sonucu 2 + 3 + 5 + 1 = 11 değil, 7 olur.
endingHerevebestdeğerlerininums[0]olarak ayarlamadan döngüyü 1. dizinden başlatmak.[-5]gibi tek elemanlı bir liste -5 döndürmelidir.
Sıkça sorulan sorular3
Kadane algoritması nedir?
Kadane algoritması, tek geçişte bitişik bir alt dizinin en büyük toplamını bulur. Geçerli öğede sona eren bir dizinin en iyi toplamını tutar ve her yeni öğede bu diziyi ya genişletir ya da yeni bir dizi başlatır. Bu toplamların en büyüğü yanıttır.
Maksimum Alt Dizi'nin zaman karmaşıklığı nedir?
Kadane algoritması O(n) zaman ve O(1) ek alan kullanır, çünkü her elemana bir kez bakılır. Çalışan toplamı kullanarak her alt diziyi kontrol etmek O(n²) sürer; her alt diziyi baştan toplayarak hesaplamak ise O(n³) sürer.
Maksimum Alt Dizi neden bir dinamik programlama problemidir?
i indeksinde biten bir alt dizinin en iyi toplamı, yalnızca i-1 indeksinde biten bir alt dizinin en iyi toplamına bağlıdır. Bu, indeksler üzerinde bir bağıntıdır; dinamik programlamanın yapısı budur. Kadane algoritması, tüm bir tablo yerine yalnızca en son değeri saklar; bu nedenle O(1) alan gerektirir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def maxSubArray(nums):
# Kodu buraya yazınTest #1
Test #2
Argüman
nums = [2, -4, 3, -1, 5, -6, 1]
Beklenen Çıktı
7