Prompt dan penetapan
Diberikan satu tatasusunan integer dengan panjang n yang hujungnya disambungkan ke permulaannya, sub-tatasusunan bersebelahan boleh membalut (wrap around) tetapi tidak boleh menggunakan kedudukan yang sama dua kali. Kembalikan hasil tambah maksimum bagi sub-tatasusunan bukan kosong. Penemu duga sering meminta calon untuk menerbitkan varian bulat daripada algoritma Kadane dan menerangkan sebab tatasusunan semua-negatif tidak boleh menggunakan total - minSum secara membuta tuli.
Perkara yang diuji oleh penemu duga
- Membahagikan jawapan kepada julat tanpa balutan dan julat membalut.
- Menggunakan pelengkap antara hasil tambah sub-tatasusunan maksimum dan minimum dan bukannya menduplikasi tatasusunan.
- Mengekalkan kekangan bukan kosong untuk input semua-negatif, satu elemen, dan integer terikat.
Soalan penjelasan sebelum menjawab
- Adakah sub-tatasusunan mesti bukan kosong? Ya, jadi input semua-negatif mengembalikan nilai negatif terbesarnya.
- Bolehkah sesuatu kedudukan digunakan dua kali? Tidak; julat membalut adalah pelengkap kepada satu julat tengah bukan kosong.
- Adakah kita hanya mengembalikan hasil tambah atau juga sempadan? Prompt ini meminta hasil tambah; sempadan memerlukan penyimpanan rekod indeks tambahan dan perwakilan bulat.
Rangka kerja jawapan 30 saat
Saya membahagikan jawapan kepada dua kes. Julat tanpa balutan ialah hasil tambah sub-tatasusunan maksimum biasa. Julat membalut adalah sama dengan jumlah keseluruhan tolak hasil tambah sub-tatasusunan minimum bukan kosong. Satu laluan mengekalkan hasil tambah maksimum, minimum dan jumlah keseluruhan. Jika julat minimum ialah keseluruhan tatasusunan, pelengkapnya adalah kosong, jadi saya mengembalikan maksimum biasa sebagai ganti. Algoritma ini mengambil masa O(n) dan ruang tambahan O(1).
Perincian langkah demi langkah
1. Terbitkan dua kes
Algoritma Kadane mencari julat tanpa balutan yang terbaik. Julat membalut terdiri daripada akhiran dan awalan; pelengkapnya ialah satu julat tengah bersebelahan bukan kosong, jadi hasil tambahnya ialah total - minSubarray. Mengambil calon yang lebih besar meliputi setiap julat yang sah.
2. Kekalkan varian tak berganjak Kadane
Pada nilai x, keadaan biasa menyimpan hasil tambah terbaik yang berakhir pada kedudukan semasa; keadaan minimum menyimpan hasil tambah terkecil yang berakhir di situ. Kemas kini setiap satu daripada keadaan semasa sebelumnya, kemudian kemas kini nilai ekstrem global. Mulakan maksimum global kepada infiniti negatif dan minimum kepada infiniti positif supaya tatasusunan negatif satu elemen tidak dianggap sebagai kosong.
3. Kendalikan input semua-negatif
Apabila setiap nilai adalah negatif, sub-tatasusunan minimum ialah keseluruhan tatasusunan dan total - minSubarray adalah sifar, yang mewakili julat kosong dan melanggar syarat prompt. Kembalikan maksimum biasa apabila hasil tambah terbaik adalah negatif. Menjejaki sama ada julat minimum meliputi keseluruhan tatasusunan adalah satu lagi pelaksanaan yang sah, tetapi semakan tanda adalah lebih mudah.
4. Kod dan kerumitan
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 dilawati sekali: masa O(n) dan ruang tambahan O(1). Gunakan jenis integer yang lebih luas apabila integer mesin bahasa pengaturcaraan mungkin melimpah untuk jumlah keseluruhan atau hasil tambah perantara.
5. Contoh balas dan pengesahan
[5,-3,5] mempunyai jawapan membalut sebanyak 5 + 5 = 10. [-3,-2,-3] mesti mengembalikan -2, bukan sifar. Untuk [1,-2,3,-2], jawapan biasa ialah 3 dan calon membalut tidak boleh melebihinya. Ujian juga harus merangkumi satu elemen, input semua-positif, julat yang bersamaan dengan keseluruhan tatasusunan bulat, dan hasil tambah yang menghampiri had integer.
Contoh jawapan berkualiti tinggi
“Saya mula-mula mengasingkan julat yang merentasi sempadan daripada julat yang tidak merentasinya. Kes tanpa balutan ialah maksimum Kadane. Julat membalut ialah jumlah keseluruhan tatasusunan tolak julat tengah minimum bukan kosong, jadi saya mengekalkan keadaan Kadane maksimum dan minimum dalam satu laluan. Jika setiap nilai adalah negatif, julat minimum ialah keseluruhan tatasusunan dan pelengkapnya adalah kosong, jadi saya mengembalikan maksimum biasa. Ini menggunakan masa O(n) dan ruang O(1), dengan ujian untuk satu nilai, semua negatif, positif membalut, dan had integer.”
Kesilapan lazim
- Menjalankan Kadane biasa pada tatasusunan pendua → sesuatu kedudukan mungkin digunakan dua kali → batasi tetingkap atau terbitkan kes pelengkap.
- Sentiasa mengembalikan
total - minSum→ input semua-negatif menghasilkan julat kosong sifar → kendalikan cabang terbaik-negatif terlebih dahulu. - Membenarkan julat minimum kosong → formula pelengkap kehilangan kekangan bukan kosong → mulakan Kadane minimum daripada elemen sebenar.
- Menyatakan O(n) tanpa varian tak berganjak → liputan kes sempadan tidak terbukti → takrifkan kedua-dua kes julat dan setiap keadaan.
Soalan susulan dan respons
Bagaimanakah anda mengembalikan kedudukan mula dan tamat?
Catat sempadan untuk kedua-dua keadaan maksimum dan minimum. Jawapan membalut ialah pelengkap julat minimum, diwakili sebagai [minEnd+1,n-1] dan [0,minStart-1]; tentukan sama ada API mengembalikan dua pecahan linear atau permulaan dan panjang bulat.
Bagaimanakah kod akan berubah jika sub-tatasusunan kosong dibenarkan?
Jawapannya sekurang-kurangnya sifar, jadi hasil tambah semasa boleh ditetapkan semula kepada sifar. Itu mengubah semantik semua-negatif; sahkan prompt sebelum menggunakan varian Kadane yang membenarkan kosong.
Bolehkah anda mengemas kini jawapan dalam O(1) untuk penstriman dinamik?
Menambah pada satu hujung boleh mengekalkan nilai awalan, akhiran dan ringkasan, tetapi memadamkan elemen lama sewenang-wenangnya membatalkan nilai ekstrem. Segment tree atau ringkasan blok mungkin diperlukan. Jelaskan arah kemas kini, kadar pertanyaan, dan sama ada anggaran dibenarkan.
Bagaimana jika sub-tatasusunan mesti mempunyai panjang tepat k?
Formula pelengkap tidak lagi terpakai kerana panjang pelengkap dikekang. Anggap tatasusunan sebagai jujukan panjang-2n, kekalkan tetingkap panjang-k dengan prefix sums atau deque, dan hadkan tetingkap pada n; kerumitan bergantung pada corak pertanyaan.