Subsekuens Naik Terpanjang
DP O(n^2), lalu trik O(n log n)
Subsekuens Naik Terpanjang adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 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 Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa Itu LIS
Suburutan mempertahankan urutan, tetapi dapat melewati elemen. Suburutan menaik terpanjang adalah suburutan terpanjang yang nilainya terus meningkat secara ketat.
a = [3, 1, 4, 1, 5, 9, 2]Suburutan, Bukan Sublarik
Berbeda dari sublarik, LIS tidak harus berurutan tanpa terputus. Anda dapat melewati angka-angka yang lebih kecil agar rantainya terus bertambah.
Keadaan DP O(n^2)
Misalkan dp[i] adalah panjang LIS yang berakhir pada indeks i. Setiap elemen setidaknya merupakan suburutan dengan panjang satu jika berdiri sendiri.
dp = [1] * nTransisi O(n^2)
Untuk setiap i, periksa semua j sebelumnya. Jika a[j] lebih kecil, lanjutkan suburutan: dp[i] = max(dp[i], dp[j] + 1).
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)Baca Jawabannya
Hasilnya adalah nilai terbesar dalam tabel, karena LIS dapat berakhir di mana saja, bukan hanya pada indeks terakhir.
answer = max(dp)Mengapa O(n^2) Dapat TLE
Perulangan ganda membutuhkan biaya O(n kuadrat). Untuk n yang mendekati 100000, proses ini terlalu lambat dan menghasilkan vonis batas waktu.
Gagasan Kesabaran
Metode yang lebih cepat menyimpan daftar ujung terkecil yang mungkin untuk setiap panjang suburutan, seperti dalam pengurutan kartu.
tails = []Gunakan Pencarian Biner untuk Menempatkan
Untuk setiap angka, cari dengan pencarian biner tempat yang sesuai di antara ujung-ujung tersebut menggunakan bisect_left, sehingga totalnya menjadi O(n log n).
from bisect import bisect_leftPerpanjang atau Ganti
Jika posisinya berada setelah akhir, gunakan append untuk memperbesar LIS. Jika tidak, timpa ujung tersebut dengan nilai yang lebih kecil.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xPanjang Tersimpan dalam Ekor
Ketika pemindaian selesai, len(tails) adalah panjang LIS. Larik itu sendiri belum tentu merupakan suburutan; hanya panjangnya yang selalu tepat.
answer = len(tails)Menaik Ketat dan Tidak Menurun
Untuk varian tidak menurun, ganti dengan bisect_right agar nilai yang sama dapat memperpanjang rantai.
from bisect import bisect_rightPemeriksaan Cepat
Metode mana yang menemukan panjang LIS dalam O(n log n)?
Rangkuman: Dari n^2 ke n log n
Sekarang Anda dapat menyelesaikan LIS dengan dua cara. DP O(n^2) sederhana, sedangkan metode ekor dan pencarian biner dapat menangani masukan besar serta melewati batas waktu.
Belajar Coding Interview Prep dengan tutor AI — gratis
Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Subsekuens Naik Terpanjang” gratis?
Ya — teks lengkap “Subsekuens Naik Terpanjang” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Subsekuens Naik Terpanjang”?
DP O(n^2), lalu trik O(n log n) Kamu berlatih Coding 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 Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding 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 4 dari 4.
Berapa lama pelajaran “Subsekuens Naik Terpanjang” 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 Coding Interview Prep ini?
Ya. Setiap pelajaran Coding 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
- Memoisasi vs Tabulasi
- Mendefinisikan State dan Transisi
- Menaiki Tangga & Kombinasi Koin
- Subsekuens Naik Terpanjang