source: https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/
C/C++ Solution to LeetCode problem 363. Max Sum of Rectangle No Larger Than K.
Problem
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
.
Examples
Example 1:
Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2Explanation: 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
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int rows = matrix.size();
int cols = matrix[0].size();
bool end = false;
int max = -INT_MAX;
for (int r = 0; r < rows; r += 1) {
int cSum = 0;
for (int c = 0; c < cols; c += 1) {
cSum += matrix[r][c];
matrix[r][c] = r == 0 ? cSum : (cSum + matrix[r - 1][c]);
for (int r1 = r; r1 >= 0; r1 -= 1) {
for (int c1 = c; c1 >= -1; c1 -= 1) {
int tmp = matrix[r][c];
if (c1 == c && r1 == r) {}
else {
if (r == 0 && c1 != c && c1 >= 0) {
tmp -= matrix[r][c1];
} else {
if (c > 0 && c1 >= 0)
tmp -= matrix[r][c1];
if (r > 0 && r1 >= 0)
tmp -= matrix[r1][c];
if (c > 0 && r > 0 && r1 >= 0 && c1 >= 0)
tmp += matrix[r1][c1];
}
}
if (tmp >= max && tmp <= k) {
max = tmp;
}
if (max == k) {
end = true;
break;
}
}
if (end)
break;
}
if (max == k) {
end = true;
break;
}
}
if (end)
break;
}
return max;
}
};