- Sedang diisi
- Dibaca
- Jawaban
Subbarisan naik terpanjang (LIS)
Dari sebuah daftar angka, berapa banyak angka yang bisa dipilih dengan urutan tetap, sehingga tiap angka lebih besar dari angka sebelumnya? Subbarisan naik terpanjang menjawab pertanyaan itu. Ketik sebuah daftar dan lihat pemrograman dinamis menghitung, untuk setiap posisi, deret terpanjang yang berakhir di sana. Tekan Putar untuk melihat tabel terisi, atau Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja. Ketik daftar angka. Untuk tiap posisi, tabel menyimpan panjang deret nilai naik terpanjang yang berakhir di sana, dan posisi sebelumnya yang dilanjutkan deret itu. Centang Izinkan nilai sama untuk deret yang tidak pernah turun. Di akhir, deret dibaca mundur dari nilai terakhirnya. Contoh baru membuat daftar lain. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.
Cara kerjanya
- Ketik daftar angka, dipisahkan koma atau spasi. Centang Izinkan nilai sama untuk deret yang tidak pernah turun.
- Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja.
- Lihat tiap posisi dibandingkan dengan setiap posisi sebelumnya, lalu lihat deret terpanjang dibaca mundur dengan warna oranye.
Cara kerja tabel
Tabel punya tiga baris: nilai, panjang subbarisan naik terpanjang yang berakhir di tiap posisi, dan posisi yang dilanjutkannya. Satu nilai saja sudah merupakan deret dengan panjang 1. Lalu setiap posisi sebelumnya diperiksa: jika nilainya lebih kecil, deret yang berakhir di sana bisa diperpanjang dengan nilai ini, sehingga panjangnya bertambah satu. Perpanjangan terpanjang yang menang, dan posisinya masuk ke baris ketiga.
Membaca deret secara mundur
Subbarisan naik terpanjang berakhir di posisi dengan panjang terbesar. Dari sana, baris ketiga menunjukkan posisi mana yang datang sebelumnya, dan baris ketiga posisi itu menunjukkan posisi sebelum itu, sampai tiba di posisi tanpa pendahulu. Jika dibaca berurutan, nilai-nilai itulah jawabannya. Jika Izinkan nilai sama dicentang, sebuah nilai juga boleh datang setelah nilai yang sama, sehingga diperoleh deret terpanjang yang tidak pernah turun.
Pertanyaan yang sering diajukan
Apa bedanya subbarisan dan subarray?
Subarray adalah satu blok nilai yang bersebelahan. Subbarisan menjaga urutan tetapi boleh melewati nilai, jadi pada 3, 10, 2, 1, 20, nilai 3, 10 dan 20 membentuk subbarisan naik meskipun 2 dan 1 berada di antaranya.
Seberapa cepat algoritma LIS?
Metode tabel membandingkan setiap pasangan posisi: n·(n − 1)/2 perbandingan untuk n nilai. Patience sorting melakukannya dalam O(n log n): untuk setiap panjang, metode ini menyimpan nilai terkecil yang mengakhiri deret sepanjang itu, dan menempatkan tiap nilai baru dengan pencarian biner.
Apakah subbarisan naik terpanjang selalu tunggal?
Tidak selalu. Pada 1, 3, 2, 4, baik 1, 3, 4 maupun 1, 2, 4 punya panjang 3. Tabel memberikan panjangnya, dan pembacaan mundur menemukan salah satunya.
Di mana subbarisan naik terpanjang digunakan?
Dalam membandingkan berkas dan genom, ketika beberapa metode lebih dulu mencari baris yang cocok lalu mengambil subbarisan naik dari posisinya; dalam penjadwalan dan teka-teki menumpuk kotak; dan dalam matematika, ketika panjang LIS dari susunan acak menjadi objek kajian yang terkenal.
Apakah ada data yang dikirim ke mana pun?
Tidak. Semuanya dihitung di browser, dan pengaturan terakhir disimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor