Description
Given a 2D matrix and integer k, find the max sum rectangle with sum no larger than k. Return the max sum.
Examples
Input:
matrix = [[1,0,1],[0,-2,3]], k = 2Output:
2Explanation:
Sum of [0,1] is 1, [1,0,1] is 2.
Input:
matrix = [[1]], k = 2Output:
1Explanation:
Minimal case with a single-element matrix.
Input:
matrix = [[2,1,-3,-1],[0,3,2,1],[1,-2,4,-1]], k = 6Output:
6Explanation:
The maximum rectangle sum not exceeding k=6 is 6.
Constraints
- •
1 ≤ m, n ≤ 100