Maximum Sum Subarray of Size K

Q: Sabit boyutlu kayan pencere nedir?

Dizi boyunca her seferinde bir adım ilerleyen, tam olarak k komşu elemandan oluşan bir aralıktır. Her konumda aralığı baştan hesaplamak yerine, değişen bir değeri güncellersiniz: sağdan giren elemanı ekler ve soldan çıkan elemanı çıkarırsınız. Böylece O(n·k) iş, O(n) işe dönüşür.

Q: Boyutu k olan maksimum toplamlı alt dizinin zaman karmaşıklığı nedir?

Kayan pencere kullanıldığında zaman karmaşıklığı O(n) , ek alan karmaşıklığı ise O(1) olur: ilk pencereyi toplamak için bir geçiş, ardından her adımda bir toplama ve bir çıkarma yapılır. Her pencereyi ayrı ayrı toplamak (n-k+1) × k toplama işlemi gerektirir; bu da O(n·k) olur ve n = 10^4 ile k = 5000 için yaklaşık 2.5 × 10^7 işlem demektir.

Q: Maksimum alt dizi probleminden farkı nedir?

Burada uzunluk k olarak sabittir; bu yüzden her aday bir penceredir ve kayan toplam hepsini kapsar. Maksimum alt dizi probleminde uzunluk serbesttir ve Kadane algoritmasına ihtiyaç duyarsın; bu algoritma her öğede mevcut diziyi genişletmeye mi yoksa yeni bir dizi başlatmaya mı karar verir. Sabit bir pencerenin böyle bir seçeneği yoktur.

Q: Önek toplamları da bunu çözebilir mi?

Evet. prefix[i] değerini ilk i elemanın toplamı olarak oluştur; s konumunda başlayan pencerenin toplamı prefix[s+k] - prefix[s] olur. Bu da O(n) zaman alır, ancak n+1 toplamı saklar. Kayan pencere aynı toplamları iki değişkenle elde eder.

KolayKayan pencere

+10

Bir tamsayı dizisi nums ve k uzunluğunda bir pencere alırsın. Tam olarak k komşu elemandan oluşan her ardışık gruba bak ve bunların arasındaki en büyük toplamı döndür. Değerler negatif olabilir, dolayısıyla yanıt da negatif olabilir.

Fonksiyon

maxSumSubarray(nums: integer-array, k: integer) → integer

numsinteger-array: tamsayı dizisi
kinteger: her pencerenin kaç komşu öğe içerdiği
Döndürürinteger: ardışık herhangi k elemanın en büyük toplamı

Kısıtlar

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴

Örnekler

Girdi: nums = [4, -1, 3, 7, -2, 5, 1]k = 3
Çıktı: 10
Açıklama: Uzunluğu 3 olan beş pencerenin toplamı 6, 9, 8, 10 ve 4 eder. En büyüğü 7 + (-2) + 5 = 10 şeklindedir.

Girdi: nums = [-3, -8, -1, -6]k = 2
Çıktı: -7
Açıklama: Her değer negatiftir, dolayısıyla her pencere toplamı da negatiftir: -11, -9 ve -7. Bunların en büyüğü -1 + (-6) = -7 olur.

Girdi: nums = [5, -2, 4]k = 3
Çıktı: 7
Açıklama: k dizinin uzunluğuna eşit olduğunda tek bir pencere vardır: dizinin tamamı ve 5 + (-2) + 4 = 7.

Gönderirken +15 gizli test

Ek soru

En iyi pencerenin nerede başladığını da, birden fazla pencere eşit olduğunda en soldakini seçerek döndürebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

n-k+1 pencere vardır ve her birini baştan toplamak k toplama işlemi gerektirir. İşin püf noktası, komşu iki pencerenin iki eleman dışında tüm elemanları paylaşmasıdır. Pencereyi yeniden oluşturmak yerine kaydır: bir değer girer, bir değer çıkar ve her pencere toplamı iki işlem gerektirir.

Her pencereyi topla

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Bir pencere, başladığı konumla belirlenir. 0, 1 dizinlerinde başlayabilir ve n-k dizinine kadar devam edebilir; çünkü daha sonraki bir başlangıç dizinin sonunu aşar. Her başlangıç için k elemanı toplayın ve toplamı şimdiye kadarki en iyi değerle karşılaştırın.

[4, -1, 3, 7, -2, 5, 1] ve k = 3 için toplamlar 6, 9, 8, 10, 4 olur ve cevap 10'dur. En iyi değeri ilk pencerenin toplamı olarak ya da en küçük tam sayı olarak başlatın; asla 0 olarak başlatmayın: tüm değerler negatif olduğunda 0, gerçek her pencere toplamından büyük olur.

Maliyet (n-k+1) × k toplama işlemidir. k, n'nin yaklaşık yarısı olduğunda en yüksek seviyeye çıkar: n = 10^4 ve k = 5000 için bu 5001 × 5000, yani yaklaşık 2.5 × 10^7 toplama işlemidir ve bunların neredeyse tamamı önceki pencere için yapılan işlemleri tekrarlar.

Algoritma

best değerini mümkün olan en küçük değere ayarla.
0 ile n-k arasındaki her başlangıç değeri için total = 0 olarak ayarla.
nums[start] ile nums[start+k-1] arasındaki değerleri total'a ekle.
total, best'ten büyükse onu kaydet.
best'i döndür.

def maxSumSubarray(nums, k):
    n = len(nums)
    best = None
    for start in range(n - k + 1):
        total = 0
        for i in range(start, start + k):
            total += nums[i]
        if best is None or total > best:
            best = total
    return best

Sabit bir pencere kaydırın

Sezgi

0 indeksinden başlayan pencereyi 1 indeksinden başlayanla karşılaştırın. [4, -1, 3, 7, -2, 5, 1] dizisinde k = 3 için bunlar 4 + (-1) + 3 = 6 ve (-1) + 3 + 7 = 9 olur. İkisinde de -1 ve 3 bulunur. İkinci toplam, ilk toplama giren değerin, 7, eklenip çıkan değerin, 4, çıkarılmasıyla elde edilir: 6 + 7 - 4 = 9.

Bu, her adım için geçerlidir. Pencerenin sağ ucu i indeksine ilerlediğinde i konumundaki eleman pencereye girer ve i-k konumundaki eleman çıkar. Böylece ilk pencerenin toplamını bir kez hesaplar, ardından her adımda bir toplama ve bir çıkarma yaparak toplamı güncellersiniz. Toplamlar, kaba kuvvet yöntemindekiyle aynı şekilde 6, 9, 8, 10, 4 olur ve en büyüğünü tutarsınız.

Her eleman bir kez pencereye girer ve en fazla bir kez çıkar; bu nedenle zaman karmaşıklığı O(n) olur. Geçerli pencere toplamı ve en iyi toplam olmak üzere iki sayı tutarsınız; dolayısıyla ek alan karmaşıklığı O(1) olur. Buradaki hiçbir toplamın büyüklüğü 10^4 × 10^4 = 10^8 değerini aşmadığından 32 bitlik bir tamsayı yeterlidir.

Algoritma

nums[0] ile nums[k-1] arasındaki değerleri window değişkenine ekleyin.
best = window olarak ayarlayın.
k ile n-1 arasındaki her i için nums[i] değerini ekleyin ve nums[i-k] değerini çıkarın.
Her adımdan sonra best değerini best ve window değerlerinden büyük olanına ayarlayın.
best değerini döndürün.

def maxSumSubarray(nums, k):
    # Sum of the first window, nums[0..k-1].
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        # Slide one step right: nums[i] enters, nums[i-k] leaves.
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

Tuzaklar ve uç durumlar

Pencere fikri basittir; bu yüzden hatalar başlangıç değerlerinde ve indekslerde gizlenir.

best değerini 0 olarak başlatmak. [-3, -8, -1, -6] ve k = 2 için gerçek yanıt -7 olur, ancak best değeri 0 olan bir değer hiçbir zaman geçilemez ve yanıt olarak döndürülür.
Yanlış elemanı çıkarmak. nums[i] pencereye girdiğinde, pencereden çıkan eleman nums[i-k] olur. nums[i-k+1] veya nums[i-k-1] kullanmak yanlış uzunlukta pencereler oluşturur.
Kaba kuvvet yöntemini bir başlangıç noktası erken sonlandırmak. Son pencere n-k konumundan başlar, bu nedenle döngü bu konumu da içermelidir. k = n olduğunda bu tek penceredir; bir eksik adımlı hata hiçbir pencereyi kontrol etmez ve best değerinin başlangıç değerini döndürür.
Yalnızca döngüden sonra karşılaştırma yapmak. En iyi pencere ilk pencere olabilir; bu yüzden ilk toplamı da karşılaştırın veya best değerini bu toplamla başlatın.
R ve Lua'nın saymaya 1'den başladığını unutmak. İlk pencere nums[1..k] olur ve nums[i] pencereye girdiğinde çıkan eleman yine nums[i-k] olur.

Sıkça sorulan sorular4

Sabit boyutlu kayan pencere nedir?

Dizi boyunca her seferinde bir adım ilerleyen, tam olarak k komşu elemandan oluşan bir aralıktır. Her konumda aralığı baştan hesaplamak yerine, değişen bir değeri güncellersiniz: sağdan giren elemanı ekler ve soldan çıkan elemanı çıkarırsınız. Böylece O(n·k) iş, O(n) işe dönüşür.

Boyutu k olan maksimum toplamlı alt dizinin zaman karmaşıklığı nedir?

Kayan pencere kullanıldığında zaman karmaşıklığı O(n), ek alan karmaşıklığı ise O(1) olur: ilk pencereyi toplamak için bir geçiş, ardından her adımda bir toplama ve bir çıkarma yapılır. Her pencereyi ayrı ayrı toplamak (n-k+1) × k toplama işlemi gerektirir; bu da O(n·k) olur ve n = 10^4 ile k = 5000 için yaklaşık 2.5 × 10^7 işlem demektir.

Maksimum alt dizi probleminden farkı nedir?

Burada uzunluk k olarak sabittir; bu yüzden her aday bir penceredir ve kayan toplam hepsini kapsar. Maksimum alt dizi probleminde uzunluk serbesttir ve Kadane algoritmasına ihtiyaç duyarsın; bu algoritma her öğede mevcut diziyi genişletmeye mi yoksa yeni bir dizi başlatmaya mı karar verir. Sabit bir pencerenin böyle bir seçeneği yoktur.

Önek toplamları da bunu çözebilir mi?

Evet. prefix[i] değerini ilk i elemanın toplamı olarak oluştur; s konumunda başlayan pencerenin toplamı prefix[s+k] - prefix[s] olur. Bu da O(n) zaman alır, ancak n+1 toplamı saklar. Kayan pencere aynı toplamları iki değişkenle elde eder.

Python

def maxSumSubarray(nums, k):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

nums = [4, -1, 3, 7, -2, 5, 1]
k = 3

Beklenen