Subbarisan naik terpanjang (LIS)

Pilih angka dari sebuah daftar, dari kiri ke kanan, masing-masing lebih besar dari sebelumnya. Seberapa panjang rantai seperti itu bisa dibuat? Pertanyaannya cukup sederhana untuk buku teka-teki, dan jawabannya menghubungkan sebuah permainan kartu, tabel pemrograman dinamis klasik, dan salah satu hasil paling indah tentang pengacakan.

Sederet batang dengan tinggi berbeda-beda, dengan rantai batang yang naik dari kiri ke kanan ditandai warna oranye
Sederet batang dengan tinggi berbeda-beda, dengan rantai batang yang naik dari kiri ke kanan ditandai warna oranye

Masalahnya

Diberikan daftar angka, subbarisan mengambil sebagian angka itu dengan urutan aslinya. Subbarisan disebut naik jika tiap nilai lebih besar dari sebelumnya. Subbarisan naik terpanjang, atau LIS, adalah pilihan seperti itu yang paling panjang. Daftar berisi n nilai punya 2ⁿ subbarisan, jadi memeriksa semuanya hanya bisa untuk daftar yang sangat pendek.

Tabelnya

Misalkan len[i] adalah panjang subbarisan naik terpanjang yang berakhir tepat di posisi i. Nilainya 1 untuk nilai itu sendiri, atau 1 + len[j] untuk posisi j sebelumnya yang nilainya lebih kecil, mana pun yang terbesar. Tiap posisi melihat kembali semua posisi sebelumnya, jadi tabel memerlukan n·(n − 1)/2 perbandingan. Jawabannya adalah len[i] terbesar, dan dengan mencatat j mana yang menghasilkan tiap len[i], subbarisan bisa dibaca mundur.

Sebuah contoh

Ambil 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. Posisi demi posisi, panjangnya adalah 1, 2, 1, 1, 3, 2, 3, 4, 3 dan 5: 20 memperpanjang 3, 10; 4 memperpanjang 3; 6 memperpanjang 4, 7 memperpanjang 6, dan 9 memperpanjang 7. Membaca mundur dari 9 memberi 3, 4, 6, 7, 9, subbarisan naik dengan panjang 5.

Cara yang lebih cepat: patience sorting

Bagikan nilai-nilai seperti kartu ke beberapa tumpukan: tiap nilai diletakkan di tumpukan paling kiri yang kartu teratasnya tidak lebih kecil darinya, atau memulai tumpukan baru di sebelah kanan. Banyaknya tumpukan adalah panjang LIS. Karena kartu teratas tumpukan selalu terurut, tumpukan yang tepat bisa ditemukan dengan pencarian biner, sehingga seluruh metode memerlukan O(n log n) langkah. Namanya diambil dari permainan kartu solitaire (patience) yang mirip dengannya.

Sedikit matematika

Pada 1935 Paul Erdős dan George Szekeres membuktikan bahwa setiap daftar berisi n² + 1 bilangan berbeda punya subbarisan naik atau turun dengan panjang n + 1. Stanislaw Ulam bertanya pada 1961 seberapa panjang LIS dari susunan acak n bilangan. Jawabannya, mendekati 2√n untuk n besar, dipastikan pada 1977 oleh Anatoly Vershik dan Sergei Kerov serta oleh Ben Logan dan Larry Shepp, dan pada 1999 Jinho Baik, Percy Deift, dan Kurt Johansson menemukan bentuk tepat fluktuasinya: distribusi Tracy–Widom dari teori matriks acak.

Paul Erdős di sebuah seminar mahasiswa di Budapest pada tahun 1992. Pada tahun 1935 ia dan George Szekeres membuktikan bahwa setiap daftar n² + 1 bilangan berbeda memiliki subbarisan naik atau turun sepanjang n + 1.
Paul Erdős di sebuah seminar mahasiswa di Budapest pada tahun 1992. Pada tahun 1935 ia dan George Szekeres membuktikan bahwa setiap daftar n² + 1 bilangan berbeda memiliki subbarisan naik atau turun sepanjang n + 1.
Potret Stanisław Ulam
Potret Stanisław Ulam

Jelajahi

Buka aplikasinya dan tekan Langkah. Kolom oranye adalah posisi yang sedang dihitung, dan kolom biru adalah posisi sebelumnya yang dibandingkan dengannya. Baris Panjang bertambah saat deret yang lebih panjang ditemukan, baris Datang setelah mengingat dari mana deret itu berasal, dan di akhir jawabannya dibaca mundur dengan warna oranye dan ditampilkan di bawah tabel.

Pertanyaan yang sering diajukan

Berapa kompleksitas waktu LIS?

O(n²) dengan tabel, karena tiap posisi melihat setiap posisi sebelumnya, dan O(n log n) dengan patience sorting dan pencarian biner. Keduanya memerlukan memori O(n).

Bagaimana cara mencari subbarisan tak turun terpanjang?

Izinkan sebuah nilai datang setelah nilai yang sama: bandingkan dengan ≤, bukan <. Di aplikasi, centang Izinkan nilai sama. Dengan patience sorting, letakkan tiap nilai di tumpukan paling kiri yang kartu teratasnya benar-benar lebih besar.

Apa itu subbarisan turun terpanjang?

Masalah yang sama dengan perbandingan dibalik, atau LIS dari daftar yang setiap nilainya dinegatifkan. Menurut teorema Erdős–Szekeres, daftar yang cukup panjang selalu punya subbarisan naik yang panjang atau subbarisan turun yang panjang.

Seberapa panjang LIS dari daftar acak?

Untuk susunan acak dari n bilangan berbeda, mendekati 2√n untuk n besar. Koreksinya tumbuh seperti akar pangkat enam dari n, jadi untuk seribu bilangan rata-ratanya sekitar 58, sedikit di bawah 2√1000 ≈ 63.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Coba subbarisan naik terpanjang