Wawancara Coding: Jumlah Subarray Maksimum dengan Satu Penghapusan

Apa yang dievaluasi oleh pewawancara

Diberikan sebuah array integer, kembalikan jumlah maksimum dari subarray kontinu yang tidak kosong setelah menghapus paling banyak satu elemen. Penghapusan bersifat opsional, dan elemen-elemen yang tersisa harus berasal dari satu interval kontinu.

Batasan dan batasan kasus (boundaries)

• Array tidak kosong dan dapat berisi nilai negatif, nol, atau positif.
• Hasilnya tidak boleh berupa array kosong.
• Menghapus titik akhir interval sama dengan mengecualikan titik akhir tersebut dari interval yang dipilih.
• Bertujuan untuk satu kali pemindaian (one scan) daripada mengenumerasi posisi penghapusan dan dua subarray.

Ubah penghapusan menjadi sebuah status (state)

Pertahankan keep, yaitu jumlah terbaik yang berakhir pada indeks saat ini tanpa penghapusan, dan drop, yaitu jumlah terbaik yang berakhir di sana setelah satu penghapusan. Untuk sebuah nilai x, keep memilih untuk memulai ulang atau memperpanjang; drop memilih untuk menghapus x atau memperpanjang status yang sudah dihapus sebelumnya.

Pisahkan status hasil dari status perantara

Jawabannya harus memeriksa kedua status karena nilai optimum dapat menggunakan tanpa penghapusan atau menghapus nilai negatif. Menginisialisasi drop ke nol akan memungkinkan subarray kosong atau penghapusan elemen yang tidak ada.

Jelaskan kompleksitas linier

Setiap nilai memperbarui dua status berukuran konstan, sehingga waktu yang dibutuhkan adalah O(n) dan ruang tambahan adalah O(1). Status-status tersebut lengkap karena setiap interval valid yang berakhir di sini telah melakukan tanpa penghapusan atau tepat satu penghapusan.

Pertanyaan klarifikasi sebelum menjawab

• Apakah “paling banyak satu” mencakup tanpa penghapusan? Mengharuskan tepat satu penghapusan akan mengubah jawaban dan batas untuk satu elemen.
• Apakah hasilnya harus tidak kosong? Mengizinkan output kosong dapat secara salah menghasilkan nol sebagai jawaban.
• Apakah jumlahnya dapat meluap (overflow) dari integer 32-bit? Ini menentukan tipe akumulator dan rentang pengujian.

Kerangka jawaban 30 detik

“Saya menyimpan dua status yang berakhir pada indeks saat ini: keep tanpa penghapusan dan drop dengan satu penghapusan. Untuk x, keep adalah memulai ulang atau memperpanjang; drop adalah menghapus x atau memperpanjang drop yang lama. Jawabannya adalah nilai maksimum yang terlihat di kedua status. Saya menginisialisasi dari elemen pertama daripada nol untuk input yang semuanya bernilai negatif, mencapai waktu O(n) dan ruang O(1).”

Pembahasan mendalam langkah demi langkah

Misalkan status sebelumnya adalah keepPrev dan dropPrev. Perbarui keduanya sebagai berikut:

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

keepPrev pada baris kedua berarti menghapus elemen saat ini; interval lama sudah berisi sebuah elemen. dropPrev + x berarti penghapusan terjadi lebih awal dan nilai saat ini ditambahkan. Simpan nilai lama sebelum menimpa salah satu status.

Untuk array dengan satu elemen, keep adalah elemen tersebut dan drop tidak boleh mewakili interval kosong yang valid. Inisialisasi drop ke negatif tak hingga dan perbarui dari elemen kedua, atau tentukan semantik elemen pertama secara eksplisit sambil tetap menjaga aturan tidak kosong.

Contoh jawaban berkualitas tinggi

“Saya membagi masalah ini menjadi dua status DP. keep adalah jumlah terbaik yang berakhir pada indeks ini tanpa penghapusan; drop adalah jumlah terbaik setelah satu penghapusan. Untuk setiap x, menggunakan status lama, hitung keep=max(x, keep+x) dan drop=max(drop+x, oldKeep). Saya menginisialisasi dari nilai pertama sehingga array yang semuanya bernilai negatif tidak pernah mengembalikan nol, lalu mengambil nilai maksimum dari kedua status. Setiap nilai membutuhkan komputasi konstan, menghasilkan waktu O(n) dan ruang O(1).”

Kesalahan umum

• Menjalankan algoritma Kadane biasa tanpa status untuk penghapusan.
• Menginisialisasi drop ke nol dan mengizinkan interval kosong.
• Menghitung drop dari keep yang sudah diperbarui, menggunakan satu nilai sebanyak dua kali.
• Mengizinkan hasil kosong tanpa mengklarifikasi batasan masalah.
• Hanya menguji array bernilai positif dan melewatkan kasus semua negatif, satu elemen, serta penghapusan titik akhir.

Gejala kegagalan dan perbaikannya

Mengembalikan nol untuk [-5] melanggar aturan tidak kosong. Jika [1,-2,0,3] tidak pernah melebihi Kadane biasa, status penghapusan tidak memberikan kontribusi. Tulis invarian terlebih dahulu, lalu telusuri array kecil satu transisi demi satu transisi.

Implementasi produksi

Gunakan akumulator yang cukup besar untuk rentang input. Untuk mengembalikan interval, sertakan metadata indeks awal, indeks penghapusan, dan indeks akhir pada setiap status; jumlah status tetap konstan, tetapi pemutus seri (tie-breaking) harus deterministik.

Daftar periksa verifikasi

Uji satu elemen, semua negatif, semua positif, menghapus nilai negatif di tengah, menghapus titik akhir, beberapa nilai optimum, dan nilai maksimum. Untuk array kecil, bandingkan dengan referensi O(n²) yang mengenumerasi penghapusan opsional dan menjalankan Kadane, menggunakan uji diferensial acak.

Pertanyaan lanjutan dan jawabannya

Apa yang berubah jika satu penghapusan bersifat wajib?

Anda tidak dapat hanya mengembalikan keep, karena solusinya harus menggunakan drop. Array dengan satu elemen tidak memiliki hasil tidak kosong yang valid, sehingga API memerlukan nilai sentinel eksplisit atau panjang input minimum.

Bisakah prefix sum menyelesaikannya?

Prefix sum dapat mengenumerasi posisi penghapusan dan interval dalam O(n²). Prapemrosesan subarray maksimum kiri dan kanan mencapai O(n) dengan ruang O(n); pemindaian dua status lebih efisien dalam penggunaan ruang.

Bagaimana cara memulihkan interval sebenarnya?

Sertakan indeks awal dan indeks penghapusan pada setiap status. Atur ulang awal saat memulai ulang, catat indeks saat menghapus nilai saat ini, dan lacak balik titik akhir dari status yang menghasilkan jawaban terbaik.

Rubrik penilaian

• Definisi status: membedakan dengan jelas antara tanpa penghapusan dan satu penghapusan.
• Transisi yang benar: menggunakan status lama dan mencakup mulai ulang, perpanjangan, serta penghapusan elemen saat ini.
• Batasan lengkap: menangani kasus semua negatif, satu elemen, tidak kosong, dan luapan (overflow).
• Kompleksitas yang akurat: mencapai waktu O(n) dan ruang tambahan O(1).
• Verifikasi yang kuat: mengusulkan enumerator referensi dan pengujian yang berfokus pada batasan.

Pemeriksaan kepatuhan

Pastikan bahwa transisi status, batasan tidak kosong, dan klaim kompleksitas tetap konsisten.

Daftar periksa jawaban wawancara

Sebutkan dua invarian, tulis kedua transisi, tekankan penyimpanan nilai lama dan inisialisasi elemen pertama, lalu berikan kompleksitas dan pengujian diferensial acak.

Kesimpulan satu kalimat

Mengizinkan satu penghapusan menambahkan dimensi “sudah dihapus” ke DP status kontinu milik Kadane, menghasilkan nilai optimum tidak kosong dalam waktu linier dan ruang konstan.