Max Sum of Rectangle No Larger Than K
Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.
It is guaranteed that there will be a rectangle with a sum no larger than k.
Follow up: What if the number of rows is much larger than the number of columns?
Example 1
1 0 1 0 -2 3
Input
matrix = [[1,0,1],[0,-2,3]], k = 2Output
2The sum of the rectangle [[0, 1], [-2, 3]] is 2, and 2 is the maximum sum no larger than k.
Example 2
2 2 -1
Input
matrix = [[2,2,-1]], k = 3Output
3The subrectangle [[2, 2, -1]] has sum 3, which is no larger than k and is maximal.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -100 <= matrix[i][j] <= 100
- -10^5 <= k <= 10^5