Subarray Maksimum dan Subarray Produk Maksimum
Terapkan algoritma Kadane pada maximum-sum-subarray dan kembangkan untuk melacak nilai maksimum serta minimum pada varian hasil kali.
Subarray Maksimum dan Subarray Produk Maksimum adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Masalah Sublarik Jumlah Maksimum
Masalah Sublarik Maksimum meminta Anda menemukan sublarik bersebelahan dalam larik satu dimensi berisi angka yang memiliki jumlah terbesar. Sebagai contoh, dalam [-2, 1, -3, 4, -1, 2, 1, -5, 4], sublarik [4, -1, 2, 1] menghasilkan jumlah maksimum sebesar 6. Pendekatan pemeriksaan menyeluruh O(n²) memeriksa semua sublarik, tetapi algoritma Kadane menyelesaikannya dalam O(n).
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) # 6Intuisi Algoritma Kadane
Algoritma Kadane menelusuri larik satu kali sambil mempertahankan current_sum yang terus diperbarui. Pada setiap elemen, Anda menentukan: apakah lebih baik memperluas sublarik yang sudah ada atau memulai sublarik baru dari elemen ini? Jika current_sum menjadi negatif, nilai itu hanya akan merugikan sublarik berikutnya, jadi mulailah kembali. Relasinya adalah 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)) # 6Menelusuri Algoritma Kadane
Mari kita telusuri algoritma Kadane pada [-2, 1, -3, 4, -1, 2, 1, -5, 4]: mulai dengan curr=-2, max=-2. Pada 1: curr=max(1,-2+1)=1, max=1. Pada -3: curr=max(-3,1-3)=-2, max=1. Pada 4: curr=max(4,-2+4)=4, max=4. Pada -1: curr=3, max=4. Pada 2: curr=5, max=5. Pada 1: curr=6, max=6. Pada -5: curr=1. Pada 4: curr=5, max=6. Algoritma ini dengan benar mengidentifikasi sublarik yang berakhir pada indeks 6 sebagai sublarik optimal.
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])Mengembalikan Sublarik yang Sebenarnya
Jika pewawancara meminta Anda mengembalikan sublariknya sendiri (bukan hanya jumlahnya), Anda perlu melacak indeks awal dan akhir. Saat memulai kembali (karena num > current_sum + num), perbarui temp_start. Saat memperbarui max_sum, simpan temp_start sebagai start dan indeks saat ini sebagai end. Hal ini menambahkan beban O(1) pada algoritma O(n) yang sama.
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])Masalah Sublarik Hasil Kali Maksimum
Masalah Sublarik Hasil Kali Maksimum lebih rumit daripada varian jumlah karena adanya angka negatif. Dua angka negatif menghasilkan nilai positif saat dikalikan, sehingga hasil kali yang sangat negatif dapat menjadi maksimum setelah dikalikan dengan angka negatif lainnya. Untuk [2, 3, -2, 4], jawabannya adalah 6 ([2, 3]). Untuk [-2, 0, -1], jawabannya adalah 0. Kita harus melacak hasil kali maksimum dan minimum pada setiap langkah.
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)Melacak Hasil Kali Maksimum dan Minimum
Inti pentingnya: pada setiap posisi, hasil kali maksimum saat ini adalah salah satu dari num, max_so_far * num, atau min_so_far * num (yang terakhir membantu ketika angka negatif mengubah nilai minimum menjadi maksimum). Hal yang sama berlaku untuk nilai minimum. Perbarui keduanya, cur_max dan cur_min, secara bersamaan menggunakan nilai sebelumnya agar tidak menggunakan nilai yang sudah diperbarui pada langkah yang sama.
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])) # -2Mengapa min_prod Penting
Perhatikan [-3, -10, 5]. Setelah memproses -3: max=-3, min=-3. Setelah -10: kandidatnya adalah (-10, 30, 30) → max=30, min=-10. Setelah 5: kandidatnya adalah (5, 150, -50) → max=150. Tanpa melacak min_prod, Anda akan melewatkan pembalikan yang terjadi ketika nilai minimum yang sangat negatif dikalikan dengan angka negatif lainnya. Selalu hitung max dan min dari nilai sebelumnya yang sama untuk menghindari kesalahan pembacaan data usang.
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: 150Nol Mengatur Ulang Hasil Kali
Nol dalam larik mengatur ulang kedua hasil kali yang sedang berjalan menjadi nol, sehingga secara efektif membagi larik menjadi sublarik-sublarik yang tidak saling bergantung. Saat num = 0, baik max_prod * 0 = 0 maupun min_prod * 0 = 0, sehingga ketiga kandidat menjadi 0 dan nilai maksimum sebelumnya tetap dipertahankan. Tidak diperlukan kode kasus khusus — rumus umum menangani nol secara alami.
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])) # 0Alternatif: Pemindaian Hasil Kali Kiri-Kanan
Pendekatan alternatif menelusuri larik dari kiri ke kanan dan dari kanan ke kiri, lalu mengatur ulang hasil kali yang sedang berjalan menjadi 1 saat menemukan nol. Sublarik hasil kali maksimum tidak pernah melewati nol, jadi jika angka negatif membuat hasilnya buruk dalam satu arah, pemindaian terbalik akan menangkap pembalikan tersebut. Pendekatan ini elegan, tetapi metode pelacakan nilai minimum dan maksimum lebih umum diharapkan dalam wawancara.
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 vs Hasil Kali: Perbedaan Utama
Sublarik jumlah dan sublarik hasil kali berbeda dalam beberapa hal penting. Untuk jumlah: angka negatif selalu merugikan, jadi Anda memulai kembali secara rakus. Untuk hasil kali: dua angka negatif dapat membantu, jadi Anda harus melacak kedua nilai ekstrem. Selain itu, nol memutus hasil kali, tetapi hanya sedikit merugikan jumlah. Saat menjelaskan dalam wawancara, nyatakan perbedaan ini secara eksplisit dan jelaskan mengapa pelacakan nilai minimum diperlukan sebelum menulis kode apa pun.
# 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])) # 24Kompleksitas dan Kiat Wawancara
Baik algoritma Kadane (jumlah maksimum) maupun pelacakan nilai minimum dan maksimum (hasil kali maksimum) berjalan dalam waktu O(n) dan menggunakan ruang O(1). Kiat utama untuk wawancara: (1) Untuk jumlah maksimum, sebutkan alternatif Bagi dan Taklukkan O(n log n) untuk menunjukkan keluasan pengetahuan. (2) Untuk hasil kali maksimum, tekankan bahwa Anda memperbarui min_prod dan max_prod secara bersamaan dari nilai sebelumnya agar tidak menggunakan data usang. (3) Selalu klarifikasi: apakah larik boleh kosong? Apakah sublarik harus tidak kosong? (Ya, secara konvensi sublarik harus tidak kosong.)
# 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 negativePemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Pada pelajaran ini Anda mempelajari: algoritma Kadane menyelesaikan sublarik jumlah maksimum dalam O(n) dengan memilih untuk memperluas atau memulai kembali pada setiap elemen, sublarik hasil kali maksimum memerlukan pelacakan hasil kali minimum dan maksimum yang sedang berjalan karena pembalikan akibat angka negatif, dan nol secara alami mengatur ulang hasil kali yang sedang berjalan tanpa kode kasus khusus. Selanjutnya kita membahas masalah Pemisahan Kata menggunakan tabel DP 1D.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Subarray Maksimum dan Subarray Produk Maksimum” gratis?
Ya — teks lengkap “Subarray Maksimum dan Subarray Produk Maksimum” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Subarray Maksimum dan Subarray Produk Maksimum”?
Terapkan algoritma Kadane pada maximum-sum-subarray dan kembangkan untuk melacak nilai maksimum serta minimum pada varian hasil kali. Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Subarray Maksimum dan Subarray Produk Maksimum” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- House Robber: Rekurensi Ambil atau Lewati
- Subarray Maksimum dan Subarray Produk Maksimum
- Word Break dan Segmentasi String
- Decode Ways dan Penghitungan Jalur