Maximum Sum Subarray of Size K

Q: Berapa kompleksitas waktu subarray dengan jumlah maksimum berukuran k?

Dengan sliding window, kompleksitas waktunya O(n) dan ruang tambahan O(1) : satu penjumlahan untuk window pertama, lalu satu penambahan dan satu pengurangan pada setiap langkah. Menjumlahkan setiap window secara terpisah membutuhkan O(n·k) .

Q: Apa perbedaannya dengan masalah subarray maksimum?

Di sini panjangnya tetap k , jadi jumlah bergeser mencakup setiap kandidat. Dalam masalah subarray maksimum, panjangnya bebas, dan algoritma Kadane menentukan di setiap elemen apakah akan memperpanjang rangkaian saat ini atau memulai rangkaian baru. Window tetap tidak memiliki pilihan itu.

Q: Bisakah jumlah awalan juga menyelesaikannya?

Ya. Misalkan prefix[i] adalah jumlah dari i elemen pertama; jendela yang dimulai pada s memiliki jumlah prefix[s+k] - prefix[s] . Cara ini juga memerlukan waktu O(n) , tetapi menyimpan n+1 jumlah, sedangkan jendela geser hanya membutuhkan dua variabel.

MudahSliding window

+10

Kamu mendapatkan array bilangan bulat nums dan panjang window k. Periksa setiap rangkaian yang terdiri dari tepat k elemen berdekatan, lalu kembalikan jumlah terbesar di antaranya. Nilainya bisa negatif, jadi jawabannya juga bisa negatif.

Fungsi

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

numsinteger-array: array bilangan bulat
kinteger: berapa banyak elemen yang berdekatan dalam setiap jendela
Mengembalikaninteger: jumlah terbesar dari k elemen berurutan mana pun

Batasan

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

Contoh

Input: nums = [4, -1, 3, 7, -2, 5, 1]k = 3
Output: 10
Penjelasan: Lima jendela dengan panjang 3 memiliki jumlah 6, 9, 8, 10, dan 4. Jumlah terbesar adalah 7 + (-2) + 5 = 10.

Input: nums = [-3, -8, -1, -6]k = 2
Output: -7
Penjelasan: Setiap nilai negatif, jadi jumlah di setiap jendela juga negatif: -11, -9, dan -7. Nilai terbesar adalah -1 + (-6) = -7.

Input: nums = [5, -2, 4]k = 3
Output: 7
Penjelasan: Saat k sama dengan panjang array, hanya ada satu jendela, yaitu seluruh array, dan 5 + (-2) + 4 = 7.

Pertanyaan lanjutan

Bisakah kamu juga mengembalikan posisi awal jendela terbaik, dengan memilih yang paling kiri jika beberapa jendela memiliki nilai yang sama?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Ada n-k+1 jendela, dan menjumlahkan setiap jendela dari awal memerlukan k penjumlahan. Jendela yang bersebelahan memiliki semua elemen yang sama kecuali dua elemen, jadi geser jendela alih-alih menyusunnya kembali: satu nilai masuk, satu nilai keluar, dan setiap jumlah baru memerlukan dua operasi.

Jumlahkan setiap jendela

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Sebuah jendela ditentukan oleh posisi awalnya, dari indeks 0 hingga n-k; posisi awal yang lebih jauh akan melewati akhir. Untuk setiap posisi awal, jumlahkan k elemen, lalu bandingkan totalnya dengan nilai terbaik sejauh ini. Semua jendela diperiksa, jadi jendela terbaik pasti ditemukan.

Biayanya adalah (n-k+1) × k penjumlahan, paling besar saat k sekitar setengah dari n: 5001 × 5000, sekitar 2.5 × 10^7, untuk n = 10^4 dan k = 5000. Hampir semua penjumlahan itu mengulang pekerjaan yang sudah dilakukan untuk jendela sebelumnya.

Algoritma

Atur best ke nilai sekecil mungkin.
Untuk setiap start dari 0 hingga n-k, atur total = 0.
Tambahkan nums[start] hingga nums[start+k-1] ke total.
Jika total lebih baik daripada best, simpan nilainya.
Kembalikan best.

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

Geser jendela tetap

Intuisi

Pada contoh pertama, window yang dimulai di indeks 0 dan 1 memiliki jumlah 6 dan 9. Keduanya berisi -1 dan 3, jadi jumlah kedua adalah jumlah pertama ditambah 7 yang masuk, dikurangi 4 yang keluar: 6 + 7 - 4 = 9.

Hal itu berlaku di setiap langkah. Saat ujung kanan bergerak ke indeks i, nums[i] masuk dan nums[i-k] keluar. Jumlahkan window pertama sekali, lalu perbarui jumlahnya dengan satu penjumlahan dan satu pengurangan di setiap langkah, dan simpan jumlah terbesar yang kamu temukan.

Algoritma

Jumlahkan nums[0] hingga nums[k-1] ke dalam window.
Tetapkan best = window.
Untuk setiap i dari k hingga n-1, tambahkan nums[i] dan kurangi nums[i-k].
Setelah setiap langkah, tetapkan best ke nilai yang lebih besar antara best dan window.
Kembalikan best.

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

Jebakan dan kasus tepi

Memulai best dengan nilai 0. Untuk [-3, -8, -1, -6] dengan k = 2, nilai ini tidak pernah terkalahkan, dan kamu mengembalikan 0 alih-alih -7.
Mengurangi elemen yang salah. Saat nums[i] masuk, nums[i-k] keluar. nums[i-k+1] atau nums[i-k-1] menghasilkan jendela dengan panjang yang salah.
Berhenti satu posisi awal terlalu cepat. Jendela terakhir dimulai pada n-k. Untuk [5, -2, 4] dengan k = 3, jendela itu adalah satu-satunya jendela, dan kesalahan satu posisi membuatmu mengembalikan nilai awal best.
Hanya membandingkan di dalam perulangan. Untuk [9, 1, 1] dengan k = 2, jendela pertama, 10, adalah yang terbaik, jadi atur best ke nilai itu sebelum perulangan.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu subarray dengan jumlah maksimum berukuran k?

Dengan sliding window, kompleksitas waktunya O(n) dan ruang tambahan O(1): satu penjumlahan untuk window pertama, lalu satu penambahan dan satu pengurangan pada setiap langkah. Menjumlahkan setiap window secara terpisah membutuhkan O(n·k).

Apa perbedaannya dengan masalah subarray maksimum?

Di sini panjangnya tetap k, jadi jumlah bergeser mencakup setiap kandidat. Dalam masalah subarray maksimum, panjangnya bebas, dan algoritma Kadane menentukan di setiap elemen apakah akan memperpanjang rangkaian saat ini atau memulai rangkaian baru. Window tetap tidak memiliki pilihan itu.

Bisakah jumlah awalan juga menyelesaikannya?

Ya. Misalkan prefix[i] adalah jumlah dari i elemen pertama; jendela yang dimulai pada s memiliki jumlah prefix[s+k] - prefix[s]. Cara ini juga memerlukan waktu O(n), tetapi menyimpan n+1 jumlah, sedangkan jendela geser hanya membutuhkan dua variabel.

def maxSumSubarray(nums, k):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan