Misalkan ada sekuens: 2, 1, 3, 5, temukan bahwa urutan ascender terpanjang adalah 2, 3, 5 atau 1, 3, 5, dan panjangnya 3.
Gagasan algoritma LIS adalah:
Misalkan ada urutan a.
① Jika hanya ada satu elemen, maka panjang urutan ascender terpanjang adalah 1;
② Jika ada dua elemen, jika [1]> A [0], panjang urutan ascender terpanjang adalah 2, A [1] adalah elemen terakhir dari urutan ascender terpanjang; Jika a [1] <a [0], panjang urutan ascender terpanjang adalah 1, dan [0] dan [1] keduanya merupakan elemen terakhir dari urutan ascender terpanjangnya.
③ Jika terbuat dari tiga elemen, jika [2]> A [0], A [2]> A [1], maka A [2] dapat menjadi elemen terakhir dari sub-urutan naik terpanjang di mana [0] atau [1] berada. Kemudian urutan mana yang harus dipilih tergantung pada urutan A [0] dan [1] lebih panjang.
④ Untuk memperluas ke elemen N, itu adalah untuk melihat panjang urutan ascender terpanjang dengan [n] sebagai elemen terakhir.
Tentukan dua array, satu adalah A dan yang lainnya adalah b.
A menyimpan data asli, dan B [i] menyimpan panjang urutan ascender terpanjang yang diakhiri dengan [i].
Kodenya adalah sebagai berikut:
kelas lmax {public static void lmax (int [] a, int [] b) {b [0] = 1; untuk (int i = 1; i <a.length; i ++) {int countmax = 0; untuk (int j = 0; j <i; j ++) {if (a [i]> a [j] && b [j]> countmax) {countmax = b [j]; // Catat panjang selanjutnya yang nilai elemennya lebih kecil dari [i] tetapi sesuai dengan selanjutnya}} b [i] = countmax+1; // Panjang paling lama yang sesuai dengan [i] adalah}}}2. Keluar dari formasi
Judul Deskripsi:
Ketika di sekolah menengah, sekolah mengatur semua guru dan siswa untuk berlari setiap pagi untuk berolahraga. Setiap kali urutan latihan terdengar, semua orang mulai berlari ke bawah, dan kemudian yang tertinggal pendek berbaris di depan garis, sementara yang lebih tinggi dilapisi di ujung garis. Tiba -tiba, suatu hari, orang yang bertanggung jawab atas tim datang dengan ide dan ingin mengubah formasi. Yaitu, ketika semua orang berlari dari lantai atas, semua siswa secara acak ditempati berturut -turut, dan orang yang bertanggung jawab atas tim mengambil bagian dari siswa dari tim, sehingga ketinggian siswa yang tersisa dalam tim adalah bentuk "puncak" yang naik pertama dan kemudian turun dari depan. Dikatakan bahwa bentuk seperti itu dapat membawa keberuntungan bagi semua orang, dan saya berharap Anda semua memanjat bagian atas di jalan belajar. (Perhatikan, hanya satu sisi gunung yang memenuhi kondisi, seperti 1, 1, 2, 2, dan 1 memenuhi persyaratan)
memasuki:
Input dapat berisi beberapa sampel uji.
Untuk setiap test case, baris pertama yang dimasukkan adalah integer n (1 <= n <= 1000000): mewakili jumlah siswa yang akan dimasukkan.
Baris kedua input termasuk n bilangan bulat: mewakili tinggi siswa (cm) (bilangan bulat positif dengan tinggi tidak lebih tinggi dari 200).
Keluaran:
Untuk setiap tes, jumlah minimum siswa yang akan ditarik adalah output.
Input Sampel:
6
100 154 167 159 132 105
5
152 152 152 152 152 152
Output sampel:
0
4
Saat menggunakan LIS untuk menyelesaikan masalah ini, Anda dapat mempertimbangkan ini:
Pertama, gunakan LIS untuk menemukan panjang urutan ascender terpanjang yang berakhir dengan setiap elemen dari depan ke belakang, kemudian gunakan LIS untuk menemukan panjang urutan ascender terpanjang yang diakhiri dengan setiap elemen.
Dapatkan dua array B1, B2.
B1 dan B2 yang sesuai dengan penambahan yang sesuai dan mengurangi yang diulang adalah 'gunung' terpanjang.
Puncak kelas publik {public static void main (string [] args) {int n; int re; do {pemindai di = pemindai baru (System.in); n = in.nextInt (); } while (n <0 || n> 100000); int [] a = int int [n]; // array asli int [] ar = int new int [n]; // pemindai array terbalik di = pemindai baru (System.in); untuk (int i = 0; i <n; i ++) {a [i] = in.nextInt (); } int [] b1 = int baru [n]; @SuppressWarnings ("tidak digunakan") int [] b2 = int baru [n]; Lmax.lmax (a, b1); ar = reverse.reverse (a); Lmax.lmax (AR, B2); // Selesaikan selanjutnya dari array terbalik b2 = reverse.reverse (b2); // Balikkan selanjutnya yang menanjak dari array terbalik sehingga dapat menambahkan yang sesuai dengan yang paling lama naik setelah array asli re = hasil. Hasil (B1, B2); System.out.print (RE); }} <br> <br> <br> <br> Hasil kelas {hasil int statis public (int [] a, int [] b) {int max = 0; int [] c = int new [a.length]; untuk (int i = 0; i <a.length; i ++) {c [i] = a [i]+b [i]; } Arrays.sort (c); max = c [c.length-1] -1; // Orang yang sesuai dengan penambahan terpanjang dan mengurangi pengembalian berulang A.length-max; }}Di atas adalah semua konten dari masalah menggunakan Java untuk mengimplementasikan algoritma LIS dan membuat formasi. Saya harap ini akan membantu semua orang dan lebih mendukung wulin.com ~