题目：给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。
题目数据保证总会存在一个数值和不超过 k 的矩形区域。
题解：
前缀和暴力
代码语言：javascript复制class Solution {
public:
int sum[101][101];
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int n = matrix.size(), m = matrix[0].size();
for (int i = 1; i <= n; i ) {
for (int j = 1; j <= m; j ) {
sum[i][j] = sum[i-1][j] sum[i][j-1] - sum[i-1][j-1] matrix[i-1][j-1];
}
}
int res = INT_MIN;
for (int i = 1; i <= n; i ) {
for (int j = 1; j <= m; j ) {
for (int p = i; p <= n; p ) {
for (int q = j; q <= m; q ) {
int cur = sum[p][q] - sum[p][j-1] - sum[i-1][q] sum[i-1][j-1];
if (cur <= k)
res = max(cur, res);
}
}
}
}
return res;
}
};
前缀和 二分
类似两数之和，如果知道一个数，求另外一个数，可以放到某个数据结构中进行查询。
同样，前缀和是递增的，可以根据递增特性确定上、下、右边界，去查找左边界，如果矩阵中有负数，便不可以进行二分搜索。
代码语言：javascript复制class Solution {
public:
int sum[101][101];
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int n = matrix.size(), m = matrix[0].size();
for (int i = 1; i <= n; i ) {
for (int j = 1; j <= m; j ) {
sum[i][j] = sum[i-1][j] sum[i][j-1] - sum[i-1][j-1] matrix[i-1][j-1];
}
}
int res = INT_MIN;
for (int i = 1; i <= n; i ) { // 上
for (int j = i; j <= n; j ) { // 下
set<int> st{0};
for (int r = 1; r <= m; r ) { // 右
// 右边界与最左侧所围成的矩阵
int right = sum[j][r] - sum[i-1][r];
auto left = st.lower_bound(right - k);
if (left != st.end()) {
res = max(res, right - *left);
}
st.insert(right);
}
}
}
return res;
}
};
