363 Max Sum of Rectangle No Larger Than K
Given a non-empty 2D matrix matrix and an integer k,
find the max sum of a rectangle in the matrix such that its sum is no larger than k.
Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2,
and 2 is the max number no larger than k (k = 2).
The rectangle inside the matrix must have an area > 0.
What if the number of rows is much larger than the number of columns?
To establish a cumulative sum, refer to the previous question Range Sum Query 2D-Immutable, which can quickly find any interval sum.
When traversing to (i, j), calculate sum(i, j), which represents the sum of the rectangle (0, 0) to (i, j), and then traverse all the sub-rectangles in this rectangle, and calculate the sum and phase K Compared with this, it can traverse all the sub-rectangles of the original rectangle.