# c++ solution with prefix-sum n' binary-search, 373ms

• ``````class Solution {
public:
int lowerbound(vector<int>&vec, int val) {
int l = 0, r = (int)vec.size();
while (l < r) {
int m = l + (r-l)/2;
if (vec[m] < val) l = m+1;
else r = m;
}
return l;
}
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int h = matrix.size(), w = h ? matrix[0].size():0;
if (!w) return 0;

vector<vector<int>> csum(h+1, vector<int>(w+1,0));
for (int i = 1; i <= h; ++i) {
for (int j = 1; j <= w; ++j) {
csum[i][j] = csum[i][j-1]+csum[i-1][j]+matrix[i-1][j-1]-csum[i-1][j-1];
}
}
int rst = INT_MIN;
for (int i = 0; i < w; ++i) {
for (int j = i; j < w; ++j) {
vector<int> rsum{0};
for (int l = 1; l <= h; ++l) {
int cur = csum[l][j+1]-csum[l][i]; // rect(0,i,l-1,j)
// find max(sum[m]-sum[n] <= k); i.e., find n s.t. sum[m]-k<=sum[n]
int indx = lowerbound(rsum, cur-k); // if n exist
if (indx < rsum.size()) rst = max(rst, cur-rsum[indx]); // get max sum[m]-sum[n]
indx = lowerbound(rsum, cur); // push sum[m]
rsum.insert(rsum.begin()+indx, cur);
}
}
}
return rst;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.