Permintaan dan konteks
Diberikan array integer dengan panjang n yang ujungnya terhubung ke awal, subarray berurutan dapat melingkar (wrap around) tetapi tidak boleh menggunakan suatu posisi dua kali. Kembalikan jumlah maksimum dari subarray yang tidak kosong. Pewawancara sering meminta kandidat untuk menurunkan varian sirkular dari algoritma Kadane dan menjelaskan mengapa array yang berisi angka negatif semua tidak dapat secara langsung menggunakan total - minSum.
Hal yang diuji oleh pewawancara
- Membagi jawaban menjadi rentang tanpa wrapping dan dengan wrapping.
- Menggunakan komplemen antara jumlah subarray maksimum dan minimum alih-alih menduplikasi array.
- Mempertahankan batasan tidak kosong untuk input negatif semua, satu elemen, dan integer terbatas.
Pertanyaan klarifikasi sebelum menjawab
- Apakah subarray harus tidak kosong? Ya, sehingga input yang seluruhnya negatif mengembalikan nilai negatif terbesarnya.
- Bisakah suatu posisi digunakan dua kali? Tidak; rentang wrapping adalah komplemen dari satu rentang tengah yang tidak kosong.
- Apakah kita hanya mengembalikan jumlahnya atau juga batas-batasnya? Soal ini meminta jumlahnya; batas-batas indeks membutuhkan pencatatan indeks tambahan dan representasi sirkular.
Kerangka jawaban 30 detik
Saya membagi jawabannya menjadi dua kasus. Rentang tanpa wrapping adalah jumlah subarray maksimum biasa. Rentang dengan wrapping sama dengan jumlah total dikurangi jumlah subarray minimum yang tidak kosong. Satu kali iterasi mempertahankan jumlah maksimum, minimum, dan total. Jika rentang minimum mencakup seluruh array, komplemennya kosong, jadi saya mengembalikan nilai maksimum biasa. Algoritma ini memiliki waktu O(n) dan ruang tambahan O(1).
Pembahasan mendalam langkah demi langkah
1. Menurunkan dua kasus
Algoritma Kadane menemukan rentang tanpa wrapping terbaik. Rentang wrapping terdiri dari sufiks dan prefiks; komplemennya adalah satu rentang tengah berurutan yang tidak kosong, sehingga jumlahnya adalah total - minSubarray. Mengambil nilai yang lebih besar dari kandidat-kandidat ini mencakup setiap rentang yang sah.
2. Mempertahankan invarian Kadane
Pada nilai x, state biasa menyimpan jumlah terbaik yang berakhir pada posisi saat ini; state minimum menyimpan jumlah terkecil yang berakhir di sana. Perbarui masing-masing dari state saat ini sebelumnya, lalu perbarui nilai ekstrem global. Inisialisasi maksimum global ke tak hingga negatif dan minimum ke tak hingga positif agar array negatif satu elemen tidak dianggap kosong.
3. Menangani input bernilai negatif semua
Ketika setiap nilai negatif, subarray minimum adalah seluruh array dan total - minSubarray bernilai nol, yang merepresentasikan rentang kosong dan melanggar aturan soal. Kembalikan nilai maksimum biasa setiap kali jumlah terbaik bernilai negatif. Melacak apakah rentang minimum mencakup seluruh array adalah implementasi valid lainnya, tetapi pemeriksaan tanda lebih sederhana.
4. Kode dan kompleksitas
from typing import List
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
total = 0
current_max = current_min = 0
best_max = float("-inf")
best_min = float("inf")
for value in nums:
total += value
current_max = max(value, current_max + value)
best_max = max(best_max, current_max)
current_min = min(value, current_min + value)
best_min = min(best_min, current_min)
if best_max < 0:
return int(best_max)
return int(max(best_max, total - best_min))Setiap elemen dikunjungi satu kali: waktu O(n) dan ruang tambahan O(1). Gunakan tipe integer yang lebih lebar jika machine integer bahasa pemrograman dapat mengalami overflow untuk jumlah total atau jumlah perantara.
5. Contoh tandingan dan verifikasi
[5,-3,5] memiliki jawaban wrapping 5 + 5 = 10. [-3,-2,-3] harus mengembalikan -2, bukan nol. Untuk [1,-2,3,-2], jawaban biasa adalah 3 dan kandidat wrapping tidak dapat melebihi nilai tersebut. Pengujian juga harus mencakup satu elemen, input positif semua, rentang yang setara dengan seluruh array sirkular, dan jumlah yang mendekati batas integer.
Contoh jawaban berkualitas tinggi
“Saya pertama-tama memisahkan rentang yang melintasi batas dari yang tidak. Kasus tanpa wrapping adalah maksimum Kadane. Rentang wrapping adalah jumlah total array dikurangi rentang tengah minimum yang tidak kosong, jadi saya mempertahankan state Kadane maksimum dan minimum dalam satu kali iterasi. Jika setiap nilai negatif, rentang minimum adalah seluruh array dan komplemennya kosong, jadi saya mengembalikan maksimum biasa. Ini membutuhkan waktu O(n) dan ruang O(1), dengan pengujian untuk satu nilai, negatif semua, positif wrapping, dan batas integer.”
Kesalahan umum
- Menjalankan Kadane biasa pada array yang diduplikasi → suatu posisi dapat digunakan dua kali → batasi jendela atau turunkan kasus komplemen.
- Selalu mengembalikan
total - minSum→ input negatif semua menghasilkan rentang kosong nol → tangani cabang nilai terbaik negatif terlebih dahulu. - Mengizinkan rentang minimum kosong → rumus komplemen kehilangan batasan tidak kosong → mulai Kadane minimum dari elemen nyata.
- Menyatakan O(n) tanpa invarian → cakupan kasus batas tidak terbukti → definisikan kedua kasus rentang dan setiap state.
Pertanyaan lanjutan dan tanggapan
Bagaimana cara Anda mengembalikan posisi awal dan akhir?
Catat batas untuk state maksimum dan minimum. Jawaban wrapping adalah komplemen dari rentang minimum, direpresentasikan sebagai [minEnd+1,n-1] dan [0,minStart-1]; tentukan apakah API mengembalikan dua bagian linier atau awal sirkular beserta panjangnya.
Bagaimana kode akan berubah jika subarray kosong diizinkan?
Jawabannya setidaknya nol, sehingga jumlah saat ini dapat direset ke nol. Itu mengubah semantik kasus negatif semua; konfirmasikan soal sebelum menggunakan varian Kadane yang mengizinkan array kosong.
Bisakah Anda memperbarui jawaban dalam O(1) untuk streaming dinamis?
Menambahkan elemen di satu ujung dapat mempertahankan nilai prefiks, sufiks, dan ringkasan, tetapi menghapus elemen lama arbitrer akan membatalkan nilai ekstrem. Segment tree atau ringkasan blok mungkin diperlukan. Perjelas arah pembaruan, laju kueri, dan apakah aproksimasi diizinkan.
Bagaimana jika subarray harus memiliki panjang tepat k?
Rumus komplemen tidak lagi berlaku karena panjang komplemen dibatasi. Perlakukan array sebagai urutan dengan panjang 2n, pertahankan jendela dengan panjang k menggunakan prefix sums atau deque, dan batasi jendela pada n; kompleksitas bergantung pada pola kueri.