Subjujukan Menaik Terpanjang
DP O(n^2), kemudian helah O(n log n).
Subjujukan Menaik Terpanjang ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah LIS
Subsekuens mengekalkan susunan tetapi melangkau elemen. Subsekuens meningkat yang terpanjang ialah rantaian sedemikian yang meningkat secara ketat.
a = [3, 1, 4, 1, 5, 9, 2]Subsekuens, Bukan Sublarik
Berbeza daripada sublarik, LIS tidak semestinya bersebelahan. Anda boleh melangkaui nombor yang lebih kecil untuk memastikan rantaian terus meningkat.
Keadaan DP O(n^2)
Biarkan dp[i] menjadi panjang LIS yang berakhir pada indeks i. Setiap elemen sekurang-kurangnya membentuk subsekuens dengan panjang satu secara bersendirian.
dp = [1] * nPeralihan O(n^2)
Bagi setiap i, lihat setiap j yang terdahulu. Jika a[j] lebih kecil, panjangkan: 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)Dapatkan Jawapan
Hasilnya ialah nilai terbesar dalam jadual kerana LIS boleh berakhir di mana-mana, bukan hanya pada indeks terakhir.
answer = max(dp)Mengapa O(n^2) Boleh Menyebabkan TLE
Gelung berganda mengambil masa O(n kuasa dua). Apabila n menghampiri 100000, kaedah ini terlalu perlahan dan akan menerima keputusan had masa.
Idea Pengisihan Sabar
Kaedah yang lebih pantas menyimpan senarai hujung terkecil yang mungkin bagi setiap panjang subsekuens, seperti dalam pengisihan secara sabar.
tails = []Gunakan Carian Binari untuk Menempatkan
Bagi setiap nombor, cari secara binari kedudukannya antara hujung menggunakan bisect_left, lalu memperoleh jumlah masa O(n log n).
from bisect import bisect_leftPanjangkan atau Gantikan
Jika kedudukannya melepasi penghujung, gunakan append untuk memanjangkan LIS. Jika tidak, gantikan hujung itu dengan nilai yang lebih kecil.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xPanjang Tersimpan dalam Hujung
Apabila imbasan tamat, len(tails) ialah panjang LIS. Senarai itu sendiri tidak semestinya merupakan subsekuens; hanya panjangnya yang tepat.
answer = len(tails)Tegas berbanding Tidak Menurun
Untuk variasi tidak menurun, tukar kepada bisect_right supaya nilai yang sama boleh memanjangkan rantaian.
from bisect import bisect_rightSemakan Pantas
Kaedah manakah yang mencari panjang LIS dalam O(n log n)?
Imbas Kembali: Daripada n^2 kepada n log n
Anda kini boleh menyelesaikan LIS dengan dua cara. DP O(n^2) adalah mudah; kaedah hujung-dan-carian-binari boleh mengendalikan masukan besar dan mengatasi had masa.
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Subjujukan Menaik Terpanjang” percuma?
Ya — teks penuh “Subjujukan Menaik Terpanjang” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Subjujukan Menaik Terpanjang”?
DP O(n^2), kemudian helah O(n log n). Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Subjujukan Menaik Terpanjang” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Memoisasi berbanding Jadualan
- Tentukan Keadaan dan Peralihan
- Mendaki Tangga dan Gabungan Syiling
- Subjujukan Menaik Terpanjang