# Shed some light on this typical solution in C++

• ### 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!

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