hardDynamic Programming 2DPure DSA~48 min
Largest Submatrix Sum Not Exceeding K
A revenue grid records contribution per cell. Subject to a budget K, find the maximum total of any axis-aligned submatrix whose sum does not exceed K.
Problem
Given an m x n matrix and an integer k, return the maximum 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.
Input
An m x n integer matrix and an integer k. Values may be negative.
Output
An integer: the maximum submatrix sum that is <= k.
Constraints
- 1 <= m, n <= 100
- -100 <= matrix[i][j] <= 100
- -10^5 <= k <= 10^5
Examples
Example 1
Input
matrix = [[1,0,1],[0,-2,3]], k = 2
Output
2
The rectangle [[0,1],[-2,3]] sums to 2, the largest <= 2.
Example 2
Input
matrix = [[2,2,-1]], k = 3
Output
3
Columns 0..1 sum to 4 (>3); column 0 sums to 2; the [2,2,-1] prefix-pair giving 3 is best.