Barisan Naik Terpanjang
Cari panjang subbarisan naik terpanjang untuk data yang besar.
Pelatih atletik ingin memilih peserta dari barisan siswa, tanpa mengubah urutan berdirinya, sehingga tinggi badan yang terpilih terus naik dari kiri ke kanan. Berapa banyak siswa paling banyak yang bisa dipilih?
Masukan
Baris pertama berisi N (1 sampai 20000). Baris kedua berisi N bilangan bulat.
Keluaran
Panjang subbarisan naik ketat terpanjang.
Contoh masukan dan keluaran
Contoh 1
Masukan
8 10 9 2 5 3 7 101 18
Keluaran
4
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Cara pemrograman dinamis biasa, yaitu membandingkan setiap pasangan, butuh sekitar 200 juta langkah untuk 20000 data. Terlalu lambat.
Petunjuk 2
Simpan list ujung, dengan ujung[k] berisi nilai akhir terkecil dari subbarisan naik sepanjang k + 1. Untuk setiap angka, cari dengan pencarian biner posisi pertama yang tidak lebih kecil darinya, lalu ganti atau tambahkan.