This article mainly studies the content related to the largest submatrix in Java programming arrays, as detailed below.
Meeting a good person can change your life; meeting a good book, isn’t it?
Recently, I had a lot of insights when I read Mr. Zuo Chengyun's " The Optimal Solutions for the Algorithm and Data Structure Questions of the Programmer Code Interview Guide " . It is recommended that bloggers who have hobbies in this area also go and watch.
The algorithm of the largest matrix of the stack-based array explained in the book is very classic, but the blogger has limited ability and has not been able to thoroughly understand the essence of the algorithm. However, based on this idea, the blogger came up with a simple algorithm to deal with this type of problem, which is summarized as follows.
Core idea
Let’s take a look at a picture first, and we can roughly understand it.
As shown in the figure, each round is an operation, and our core is the internal operation for each round.
Calculate the maximum length of each layer continuously and uninterrupted
In other words, we are the most important array to calculate the bottom to top rounds, and then we can calculate the area of the continuous maximum submatrix that can be obtained in this round for each round. Then you only need to compare the largest data for each round, and return to find the area of the largest continuous submatrix of the array.
Code
Okay, with the above core ideas laid out, we can start writing code. (Although I don’t think I’ve said it very clearly, please forgive me).
package stack_and_queue;/** * @author Guo Pu<br> * Calculate the area of the largest continuous rectangle area based on the array*/public class MaxRectangle {public static void main(String[] args) {Integer[] arr = { 2, 1, 3, 5, 7, 6, 4 };Integer maxRectangle = 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 loss of the previous part of the data for (int j = 1; j <= arr.length; j++) {if (arr[j - 1] >= i) {templen += 1;templen_max = templen;} else {templen = 0;}}result[i - 1] = i * templen_max;// System.out.println(""th" + i + "The maximum continuous and uninterrupted length of the layer is: " + templen_max);}// Find the number with the largest numerical value in the result set array, that is, the area of the largest rectangular domain in the continuity area found int maxArea = 0;for (int i = 0; i < result.length; i++) {maxArea = maxArea > result[i] ? maxArea : result[i];}// Return the area of the maximum continuous rectangle field obtained by returning maxArea;}}The comments in the code are also relatively comprehensive, so I won't go into too much detail.
test
The following is a test of the array. First, let’s test it with the array shown in the picture at the beginning of this article.
Integer[] arr = {2,1,3,5,7,6,4}・・・・The area of the largest continuous rectangular area in the array is: 16
Then we modify the values of elements in the array to further test to see if the results are correct.
Integer[] arr = {2,1,3,1,7,6,4}・・・・The area of the largest continuous rectangular area in the array is: 12
After the blogger himself tested it, the algorithm works normally. :)
Optimization part
Speaking of the optimization part, the first thing we can see is to find the maximum value in the result set array in the last step.
Indeed, we can actually apply another variable to record the area of the largest submatrix of the round so far. However, this optimization does not play a big role, and there is no significant improvement in the time complexity.
Another point, I think the better entry point is to add a judgment when performing calculations for each round to decide whether to cycle downward before the current round. If the elements in the array fluctuate greatly, the optimization level is still very good.
Summarize
This small algorithm is more exquisite, and the only thing that is more flawed is that the time complexity is slightly more intense. If readers are looking for an algorithm with a relatively low time complexity, please take a detour.
It's pretty good if you just want to find a result. At least it is much more efficient than the violent method of computing.
The above is all the content of this article about the simple solution to the maximum submatrix in Java programming arrays. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!