## Algorithm

Problem Name: 363. 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`.

Example 1:

```Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).
```

Example 2:

```Input: matrix = [[2,2,-1]], k = 3
Output: 3
```

Constraints:

• `m == matrix.length`
• `n == matrix[i].length`
• `1 <= m, n <= 100`
• `-100 <= matrix[i][j] <= 100`
• `-105 <= k <= 105`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int lower_bound(int *set, int len, int x) {
int i;
for (i = 0; i  <  len; i ++) {
if (set[i] >= x) break;  // first one not less than k
}
return i;
}
int maxSumSubmatrix(int** matrix, int matrixRowSize, int matrixColSize, int k) {
int *sum_on_row, sum, max;
int *predecessor, len, i, j;
int left, right, row;
int *buff;

buff = malloc((matrixRowSize * 2 + 1) * sizeof(int));
//assert(buff);
sum_on_row = &buff[0];
predecessor = &buff[matrixRowSize];

max = 0x80000000;
for (left = 0; left  <  matrixColSize; left ++) {
memset(sum_on_row, 0, matrixRowSize * sizeof(int));
for (right = left; right  <  matrixColSize; right ++) {
len = 0;
predecessor[len ++] = 0;
sum = 0;
for (row = 0; row  <  matrixRowSize; row ++) {
sum_on_row[row] += matrix[row][right];
sum += sum_on_row[row];

// find max sum no larger than k
i = lower_bound(predecessor, len, sum - k);
if (i  <  len) {
if (max < sum - predecessor[i]) {
max = sum - predecessor[i];
}
}
i = lower_bound(predecessor, len, sum);
for (j = len; j > i; j --) {
predecessor[j] = predecessor[j - 1];
}
/*if (i  <  len) {
memcpy(&predecessor[i + 1], &predecessor[i], (len - i) * sizeof(int));
}*/
predecessor[i] = sum;
len ++;
}
}
}

free(buff);

return max;
}
``````
Copy The Code &

Input

cmd
matrix = [[1,0,1],[0,-2,3]], k = 2

Output

cmd
2

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const maxSumSubmatrix = function(matrix, k) {
const row = matrix.length,
col = matrix[0].length
let result = -Infinity
for (let i = 0; i  <  col; i++) {
let rowSum = Array(row).fill(0)
for (let j = i; j  <  col; j++) {
let sum = 0,
max = -Infinity
for (let r = 0; r  <  row; r++) {
rowSum[r] += matrix[r][j]
if (sum < 0) sum = 0
sum += rowSum[r]
max = Math.max(max, sum)
}
if (max <= k) result = Math.max(result, max)
else {
max = -Infinity
for (let m = 0; m  <  row; m++) {
sum = 0
for (let n = m; n  <  row; n++) {
sum += rowSum[n]
if (sum <= k) max = Math.max(max, sum)
}
}
result = Math.max(result, max)
}
if (result === k) return k
}
}
return result
}
``````
Copy The Code &

Input

cmd
matrix = [[1,0,1],[0,-2,3]], k = 2

Output

cmd
2

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def maxSumSubmatrix(self, matrix, k, mxTotal = -float("inf")):
for l in range(len(matrix[0])):
dp = [0] * len(matrix)
for r in range(l, len(matrix[0])):
for i in range(len(matrix)):
dp[i] += matrix[i][r]
sums, cur, mx = [float("inf")], 0, -float("inf")
for sm in dp:
bisect.insort(sums, cur)
cur += sm
mx = max(mx, cur - sums[bisect.bisect_left(sums, cur - k)])
mxTotal = max(mxTotal, mx)
return mxTotal
``````
Copy The Code &

Input

cmd
matrix = [[2,2,-1]], k = 3

Output

cmd
3
Advertisements