Maximum Sum Rectangular Submatrix in Matrix dynamic programming/2D kadane
Why Stack Overflow recommends it
Stack Overflow users link it when explaining or implementing the 2D Kadane algorithm for the maximum sum submatrix, and as a reference for related array and rectangle problems.
Recommended by 1 people across 1 different months, 2015 to 2017.
What it is
Tushar Roy walks through the maximum sum rectangle problem in a 2D matrix, building from Kadane's 1D algorithm to a 2D version that fixes left and right columns and runs Kadane over row sums. The 14-minute tutorial includes a Java implementation linked in the description.
What people said
Recommends Abhishek Divekar · 2015-08 · Stack Overflow · on “For a matrix, how many continuous submatrices exist?”
Okay so I've found an answer, it is explained really well in this video [this video] . I understood both the number of submatrices and the dynamic programming solution that implements Kadane's method to find the submatrix with the largest sum.
Cites Jerry Z. · 2016-08 · Stack Overflow · on “largest sum of contiguous subarray No Larger than k”
For example, we have {2,2,-1}, when k = 0, return -1. when k = 3, return 3. This is even tricky because we have negative numbers and an additional variable k. k can be any value, negative, don't make any assumption. I cannot refer to [LINK] and [this video] to solve this problem. Can any body help me? Better use Java or JavaScript. Here is a classic algorithm o(n) for the maximum(no variable k): public int maxSubArray(int[] nums) { int max = nums[0]; int tsum = nums[0]; for(int i=1;i<nums.length;i++){ tsum = Math.max(tsum+nums[i],nums[i]); max = Math.max(max,tsum); } return max; }
Cites TheJW · 2017-01 · Stack Overflow · on “maximum sum of sub ractangle in matrix (2D)”
I'm trying to solve the problem with finding the maximum sum of a sub rectangle in a matrix. So far I have managed to implement around 90% of the algorithm. (For any of you who do not know what I'm talking about: [this video] ) My problem is that I do not know how to remove the top or bottom values of my temp array, if they are negative. Not to mention how to know which index the deleted negative values were comming from. I have solved the problem in 1 dimension (1D) like this: int maxSoFar = 0; int maxEndingHere = 0; int i; for (i = 0; i < input.length; i++) { System.out.println(i + " + " + input[i]); if (maxEndingHere + input[i] > 0) { maxEndingHere += input[i]; } else { maxEndingHere = 0; } if
Cites dgorissen · 2017-10 · Stack Overflow · on “How can I randomly place several non-colliding rects?”
In my case I had a similar problem except that I had some pre-exiting rectangles inside the overall rectangle. So new rectangles had to be placed around those existing ones. I used a greedy approach: Rectangularize the overall (global) rectangle: create a grid from the sorted x & sorted y coordinates of all rectangles so far. So that will give you an irregular (but rectangular) grid. For each grid cell calculate the area, this gives you a matrix of areas. Use Kadanes 2D [this video] algorithm to find the sub matrix that gives you the maximum area (= the largest free rectangle) Place a random rectangle in that free space Repeat This requires a conversion from your original coordinate space to/from