Temu Duga Pengekodan: Hasil Tambah SubtatSusunan Maksimum dengan Satu Pemadaman

Perkara yang dinilai oleh penemu duga

Diberikan satu tatasusunan integer, kembalikan hasil tambah maksimum bagi subtatsusunan berdampingan yang bukan kosong selepas memadam paling banyak satu elemen. Pemadaman adalah pilihan, dan elemen-elemen yang tinggal mestilah daripada satu selang yang berdampingan.

Kekangan dan sempadan

Tatasusunan adalah bukan kosong dan mungkin mengandungi nilai negatif, sifar atau positif.
Hasilnya tidak boleh menjadi tatasusunan kosong.
Memadam titik akhir selang adalah bersamaan dengan mengecualikan titik akhir tersebut daripada selang yang dipilih.
Sasarkan satu imbasan dan bukannya menyenaraikan kedudukan pemadaman dan dua subtatsusunan.

Tukar pemadaman menjadi satu keadaan (state)

Kekalkan keep, hasil tambah terbaik yang berakhir pada indeks semasa tanpa pemadaman, dan drop, hasil tambah terbaik yang berakhir di situ selepas satu pemadaman. Untuk nilai x, keep memilih untuk memulakan semula atau melanjutkan; drop memilih untuk memadam x atau melanjutkan keadaan yang telah dipadam sebelumnya.

Asingkan keadaan hasil daripada keadaan perantaraan

Jawapan mesti memeriksa kedua-dua keadaan kerana nilai optimum mungkin tidak menggunakan sebarang pemadaman atau membuang nilai negatif. Mengogisialkan drop kepada sifar akan membenarkan subtatsusunan kosong atau pemadaman elemen yang tidak wujud.

Terangkan kekompleksan linear

Setiap nilai mengemas kini dua keadaan bersaiz malar, jadi masa adalah O(n) dan ruang tambahan adalah O(1). Keadaan-keadaan ini adalah lengkap kerana setiap selang sah yang berakhir di sini sama ada tidak melakukan pemadaman atau melakukan tepat satu pemadaman.

Soalan penjelasan sebelum menjawab

Adakah “paling banyak satu” merangkumi tiada pemadaman? Memerlukan tepat satu pemadaman mengubah jawapan dan sempadan elemen tunggal.
Adakah hasilnya mesti bukan kosong? Membenarkan output kosong boleh menyebabkan sifar menjadi jawapan yang salah.
Bolehkah hasil tambah melimpah (overflow) integer 32-bit? Ini menentukan jenis penumpuk (accumulator) dan julat ujian.

Rangka kerja jawapan 30 saat

“Saya mengekalkan dua keadaan yang berakhir pada indeks semasa: keep tanpa pemadaman dan drop dengan satu pemadaman. Untuk x, keep adalah memulakan semula atau melanjutkan; drop adalah memadam x atau melanjutkan drop yang lama. Jawapannya ialah maksimum yang dilihat dalam kedua-dua keadaan. Saya memulakan daripada elemen pertama dan bukannya sifar untuk input semua negatif, mencapai masa O(n) dan ruang O(1).”

Perbincangan mendalam langkah demi langkah

Katakan keadaan sebelumnya ialah keepPrev dan dropPrev. Kemas kini keadaan tersebut seperti berikut:

text

keep = max(x, keepPrev + x)
drop = max(dropPrev + x, keepPrev)

keepPrev pada baris kedua bermaksud memadam elemen semasa; selang lama sudah mengandungi satu elemen. dropPrev + x bermaksud pemadaman berlaku lebih awal dan nilai semasa dilampirkan. Simpan nilai lama sebelum menulis ganti mana-mana keadaan.

Untuk tatasusunan satu elemen, keep ialah elemen tersebut dan drop tidak boleh mewakili selang kosong yang sah. Mulakan drop kepada infiniti negatif dan kemas kini daripada elemen kedua, atau tentukan semantik elemen pertama yang jelas sambil mengekalkan peraturan bukan kosong.

Contoh jawapan berkualiti tinggi

“Saya membahagikan masalah kepada dua keadaan DP. keep ialah hasil tambah terbaik yang berakhir pada indeks ini tanpa pemadaman; drop ialah hasil tambah terbaik selepas satu pemadaman. Untuk setiap x, menggunakan keadaan lama, kira keep=max(x, keep+x) dan drop=max(drop+x, oldKeep). Saya memulakan daripada nilai pertama supaya tatasusunan semua negatif tidak pernah mengembalikan sifar, kemudian mengambil nilai maksimum merentas kedua-dua keadaan. Setiap nilai melibatkan kerja malar, memberikan masa O(n) dan ruang O(1).”

Kesilapan biasa

Menjalankan algoritma Kadane biasa tanpa keadaan untuk pemadaman.
Memulakan drop kepada sifar dan membenarkan selang kosong.
Mengira drop daripada keep yang telah dikemas kini, menggunakan satu nilai sebanyak dua kali.
Membenarkan hasil kosong tanpa menjelaskan sempadan masalah.
Hanya menguji tatasusunan positif dan terlepas kes semua negatif, satu elemen dan pemadaman titik akhir.

Gejala kegagalan dan pembaikan

Mengembalikan sifar untuk [-5] melanggar peraturan bukan kosong. Jika [1,-2,0,3] tidak pernah mengatasi Kadane biasa, keadaan pemadaman tidak menyumbang. Tuliskan invarian terlebih dahulu, kemudian surih tatasusunan kecil satu peralihan pada satu masa.

Pelaksanaan pengeluaran

Gunakan penumpuk yang cukup luas untuk julat input. Untuk mengembalikan selang, bawa metadata permulaan, indeks pemadaman dan penamat bersama setiap keadaan; bilangan keadaan kekal malar, tetapi pemutus seri (tie-breaking) mestilah deterministik.

Senarai semak pengesahan

Uji satu elemen, semua negatif, semua positif, memadam negatif di tengah, memadam titik akhir, berbilang optimum dan nilai maksimum. Untuk tatasusunan kecil, bandingkan dengan rujukan O(n²) yang menyenaraikan pemadaman pilihan dan menjalankan Kadane, menggunakan ujian perbezaan rawak.

Soalan susulan dan jawapan

Apakah yang berubah jika satu pemadaman adalah wajib?

Anda tidak boleh hanya mengembalikan keep, kerana penyelesaian mesti menggunakan drop. Tatasusunan satu elemen tidak mempunyai hasil bukan kosong yang sah, jadi API memerlukan sentri yang jelas atau panjang input minimum.

Bolehkah hasil tambah awalan (prefix sums) menyelesaikannya?

Hasil tambah awalan boleh menyenaraikan kedudukan pemadaman dan selang dalam O(n²). Pra-pemprosesan subtatsusunan maksimum kiri dan kanan mencapai O(n) dengan ruang O(n); imbasan dua keadaan adalah lebih cekap ruang.

Bagaimanakah anda mendapatkan semula selang sebenar?

Bawa indeks permulaan dan pemadaman bersama setiap keadaan. Tetapkan semula permulaan apabila memulakan semula, rekod indeks apabila memadam nilai semasa, dan jejak kembali penamat daripada keadaan yang menghasilkan jawapan terbaik.

Rubrik pemarkahan

Definisi keadaan: membezakan dengan jelas antara tiada pemadaman dan satu pemadaman.
Peralihan yang betul: menggunakan keadaan lama dan merangkumi permulaan semula, pelanjutan dan pemadaman elemen semasa.
Sempadan lengkap: mengendalikan kes semua negatif, satu elemen, bukan kosong dan limpahan.
Kekompleksan tepat: mencapai masa O(n) dan ruang tambahan O(1).
Pengesahan kukuh: mencadangkan penyenarai rujukan dan ujian berfokuskan sempadan.

Pemeriksaan pematuhan

Sahkan bahawa peralihan keadaan, sempadan bukan kosong dan tuntutan kekompleksan kekal konsisten.

Senarai semak jawapan temu duga

Nyatakan dua invarian, tulis kedua-dua peralihan, tekankan penyimpanan nilai lama dan pemulaan elemen pertama, kemudian berikan kekompleksan dan ujian perbezaan rawak.

Pengajaran satu ayat

Membenarkan satu pemadaman menambah dimensi “sudah dipadam” kepada DP keadaan berdampingan Kadane, menghasilkan nilai optimum bukan kosong dalam masa linear dan ruang malar.