Artikel ini terutama mempelajari konten yang terkait dengan submatrix terbesar dalam array pemrograman Java, sebagaimana dirinci di bawah ini.
Bertemu dengan orang baik dapat mengubah hidup Anda; Bertemu buku yang bagus, bukan?
Baru -baru ini, saya memiliki banyak wawasan ketika saya membaca " The The Optimal Solutions untuk Algoritma dan Pertanyaan Struktur Data dari Panduan Wawancara Kode Programmer " . Disarankan bahwa blogger yang memiliki hobi di daerah ini juga pergi dan menonton.
Algoritma matriks terbesar dari array berbasis tumpukan yang dijelaskan dalam buku ini sangat klasik, tetapi blogger memiliki kemampuan terbatas dan belum dapat memahami inti dari algoritma tersebut secara menyeluruh. Namun, berdasarkan ide ini, blogger datang dengan algoritma sederhana untuk menangani masalah jenis ini, yang dirangkum sebagai berikut.
Ide inti
Mari kita lihat gambar terlebih dahulu, dan kita dapat memahaminya secara kasar.
Seperti yang ditunjukkan pada gambar, setiap putaran adalah operasi, dan inti kami adalah operasi internal untuk setiap putaran.
Hitung panjang maksimum setiap lapisan secara terus menerus dan tidak terputus
Dengan kata lain, kami adalah array terpenting untuk menghitung bagian bawah ke atas, dan kemudian kami dapat menghitung area submatrix maksimum kontinu yang dapat diperoleh dalam putaran ini untuk setiap putaran. Maka Anda hanya perlu membandingkan data terbesar untuk setiap putaran, dan kembali untuk menemukan area submatrix kontinu terbesar dari array.
Kode
Oke, dengan ide -ide inti di atas, kita dapat mulai menulis kode. (Meskipun saya tidak berpikir saya sudah mengatakannya dengan sangat jelas, maafkan saya).
Paket stack_and_queue;/*** @author guo pu <br>* Hitung area area persegi panjang kontinu terbesar berdasarkan array*/kelas publik maxrectangle {public static main (string [] args) {integer [] arr = {2, 1, 3, 5, 7, 6, 4}; maxRectangleArea(arr);System.out.println("The area of the largest continuous rectangle area in the array is: " + maxRectangle);}/** * @param arr * @return The maximum area of the continuous rectangle area in the array*/private static Integer maxRectangleArea(Integer[] arr) {int[] result = new int[arr.length];// Calculate the array by traversing the continuous length from bottom to upwards for (int i = 1; i <= arr.length; i++) {// The temporary value of the accumulated continuous length in the current round is implemented int temple = 0;// Record the maximum continuous length at the height of this round int templen_max = 0;// The inner loop should start from the first layer, and starting from the first layer subscript will cause the Kehilangan bagian data sebelumnya untuk (int j = 1; j <= arr.length; j ++) {if (arr [j - 1]> = i) {templen += 1; templen_max = templen;} lain {templen = 0;}} hasil [i - 1] = i * Templen_Max;/ ox; " Panjang lapisan yang tidak terputus adalah: "+templen_max);} // Temukan angka dengan nilai numerik terbesar dalam array yang ditetapkan, yaitu, luas domain persegi panjang terbesar di area kontinuitas yang ditemukan pada maxarea = 0; untuk (int i = 0; i <results.length; i ++) {maxarea = 0; untuk (int i = i <result.length; i ++) {maxarea = 0; untuk (int i = i <result.length; i ++) {maxarea = 0; luas bidang persegi panjang kontinu maksimum yang diperoleh dengan mengembalikan maxarea;}}Komentar dalam kode juga relatif komprehensif, jadi saya tidak akan terlalu detail.
tes
Berikut ini adalah tes array. Pertama, mari kita mengujinya dengan array yang ditunjukkan pada gambar di awal artikel ini.
Integer [] arr = {2,1,3,5,7,6,4} ・・・・Area area persegi panjang kontinu terbesar di array adalah: 16
Kemudian kami memodifikasi nilai elemen dalam array untuk menguji lebih lanjut untuk melihat apakah hasilnya benar.
Integer [] arr = {2,1,3,1,7,6,4} ・・・・Area area persegi panjang kontinu terbesar di array adalah: 12
Setelah blogger sendiri mengujinya, algoritma bekerja secara normal. :)
Bagian Optimalisasi
Berbicara tentang bagian optimasi, hal pertama yang dapat kita lihat adalah menemukan nilai maksimum dalam array set hasil pada langkah terakhir.
Memang, kami sebenarnya dapat menerapkan variabel lain untuk merekam area submatrix terbesar dari putaran sejauh ini. Namun, optimasi ini tidak memainkan peran besar, dan tidak ada peningkatan yang signifikan dalam kompleksitas waktu.
Poin lain, saya pikir titik masuk yang lebih baik adalah menambahkan penilaian saat melakukan perhitungan untuk setiap putaran untuk memutuskan apakah akan bersepeda ke bawah sebelum putaran saat ini. Jika elemen dalam array berfluktuasi, tingkat optimisasi masih sangat baik.
Meringkaskan
Algoritma kecil ini lebih indah, dan satu -satunya hal yang lebih cacat adalah bahwa kompleksitas waktu sedikit lebih intens. Jika pembaca mencari algoritma dengan kompleksitas waktu yang relatif rendah, silakan mengambil jalan memutar.
Cukup bagus jika Anda hanya ingin menemukan hasilnya. Setidaknya itu jauh lebih efisien daripada metode komputasi kekerasan.
Di atas adalah semua konten artikel ini tentang solusi sederhana untuk submatrix maksimum dalam array pemrograman java. Saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya. Terima kasih teman atas dukungan Anda untuk situs ini!