### Solution

The most direct method is to test each possible rectangle in the matrix which will require O(n^4). Then can we do better? As we have done in one dimension array using prefix-sum, actually we can also follow that rule in two-dimension matrix:

- start from the very leftmost (the first column) till the end
- try each width till the very rightmost (the last column)
- calculate the prefix-sum for each row then the partial sum can be easily retrieved as one-dimension situation
- from the top to the bottom, collect the prefix-sum of each row then we can get the
`prefix-sum`

of the rectangle - use a set to store the
`prefix-sum`

of the rectangles and then searching`curSum-k`

via lower_bound to retrieve so-called`Max Sum of Rectangle No Larger Than K`

; as a result the whole time cost will be O(n^3*logn) now instead of O(n^4)

```
int maxSumSubmatrix(vector<vector<int>>& matrix, int k)
{
if(matrix.empty()) return 0;
int rowSize = matrix.size(), colSize = matrix[0].size();
int ret = INT_MIN;
for(int l = 0; l < colSize; ++l)
{
vector<int> sums(rowSize, 0);
for(int c = l; c < colSize; ++c)
{
for(int r = 0; r < rowSize; ++r)
sums[r] += matrix[r][c];
set<int> sums_set;
sums_set.insert(0);
int maxSum = INT_MIN, sum = 0;
for(int i = 0; i < rowSize; ++i)
{
sum += sums[i];
auto iter = sums_set.lower_bound(sum-k);
if(iter != sums_set.end()) maxSum = max(maxSum, sum-*iter);
sums_set.insert(sum);
}
ret = max(ret, maxSum);
}
}
return ret;
}
```

Always welcome new ideas and `practical`

tricks, just leave them in the comments!