Artikel ini menjelaskan implementasi Java dari algoritma selanjutnya untuk array. Bagikan untuk referensi Anda, sebagai berikut:
Masalah: Diberi array dengan panjang n, temukan sub-urutan autointrement monotonik terpanjang (tidak harus terus menerus, tetapi urutan tidak dapat kacau). Sebagai contoh: diberi array dengan panjang {1, 3, 5, 2, 4, 6, 7, 8} dengan panjang 8, kemudian urutan amplikon monotonik terpanjang adalah {1, 2, 4, 6, 7, 8} dan panjangnya adalah 6.
Ide 1: Ketika Anda melihat pertanyaan pada awalnya, banyak orang pasti akan memikirkan LCS pada pertama kalinya. Pertama -tama urutkan array menjadi array baru, dan kemudian gunakan array baru dan array asli untuk menemukan LCS untuk mendapatkan jawabannya. Banyak orang dapat membayangkan solusi ini, jadi saya tidak akan membahas detailnya.
Ide 2: Menurut ide ide 1, Anda masih harus menggunakan DP ketika Anda akhirnya menemukan LCS. Mengapa kami tidak menggunakan DP untuk menyelesaikannya secara langsung? Untuk array ARR, kami melintasi array dari belakang ke depan, dan menemukan yang terpanjang ketika selanjutnya berakhir dengan arr[i] , dan kemudian mengambil nilai maksimum di dalamnya. Anda bisa mendapatkan selanjutnya dari seluruh array. Jadi bagaimana menemukan yang paling lama diakhiri dengan arr[i] ? Ini diubah menjadi masalah DP. Untuk meminta arr[i] , Anda hanya perlu menemukan ARR paling lama dari arr[i-1] . Yaitu: max{arr[i]}=max{arr[i-1]}+1 .
Kode Implementasi Java:
kelas publik arrdemo {public static void main (string [] args) {// int [] arr = {89, 256, 78, 1, 46, 78, 8}; int [] arr = {1, 3, 5, 2, 4, 6, 7, 8}; // int [] arr = {6, 4, 8, 2, 17}; int max = 0; int maxlen = arr.length; // lintasi array dari belakang ke depan, dan temukan panjang selanjutnya yang paling lama saat diakhiri dengan arr [i] untuk (int i = arr.length-1; i> 0; i--) {int [] newarr = int int [i]; System.ArrayCopy (ARR, 0, Newarr, 0, I); int currentLength = 1 + dp (newarr, arr [i]); if (currentlength> max) max = currentLength; // Panjang terpanjang dari setelahnya terpanjang adalah panjang array asli, // karena kita tidak perlu menemukan elemen dari setelahnya, kita secara langsung mengakhiri loop untuk mengurangi waktu overhead jika (maks == maxlen) istirahat; } System.out.println (max); } public static int dp (int [] arr, int end) {// kondisi akhir rekursif if (arr.length == 1) {// Jika kurang dari akhir, itu termasuk dalam selanjutnya, panjang +1 if (arr [0] <= end) kembali 1; lain kembali 0; } // melintasi array dan menemukan posisi elemen terdekat dengan akhir dan <= end i for (int i = arr.length-1; i> = 0; i--) {if (arr [i] <= end) {// Potong array dari i, dan membentuk array baru untuk array baru = 0] untuk arrome [i-1] untuk terus menemukan recurse intersy inters in int [] untuk array baru = 0] untuk arrom [i-1] untuk melanjutkan recurse menemukan sekaris-panjang int [] untuk array baru = 0] untuk arr [i-1] untuk melanjutkan menemukan recurs finding the longy int [] untuk array baru ke array = to arr [i-1 untuk melanjutkan recursif menemukan sekaris-panjang int [ System.ArrayCopy (ARR, 0, Newarr, 0, I); // Hitung selanjutnya yang paling lama saat mengandung ARR [i] dan masing -masing setelah tidak mengandung ARR [i], masing -masing, dan ambil nilai maksimum int yang mengandung slen = dp (newarr, arr [i]) + 1; int notcontainlen = dp (newarr, end); Return containslen> notcontainlen? containslen: notcontainlen; }} // Jika tidak ada yang lebih kecil dari ujung ditemukan, panjang pengembalian adalah 0 pengembalian 0; }}Hasil Menjalankan:
6
Metode saya mungkin memakan banyak ruang karena beberapa array baru dibuka di tengah, tapi saya pikir itu tidak banyak - - saya belum menghitungnya. Jika ada yang salah, harap perbaiki.
Untuk informasi lebih lanjut tentang algoritma java, pembaca yang tertarik dengan situs ini dapat melihat topik: "struktur data java dan tutorial algoritma", "ringkasan tips node dom java", "ringkasan file operasi java dan direktori" dan "ringkasan tip operasi java cache" tips java "tips java" Tips "Java Cache Tips"
Saya harap artikel ini akan membantu pemrograman Java semua orang.