363. Max Sum of Rectangle No Larger Than K

  • 32.5%

https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/description/

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

1
2
3
4
5
6
Example:
Given matrix = [
[1, 0, 1],
[0, -2, 3]
]
k = 2

The answer is 2. Because the sum of rectangle [[0, 1], [-2, 3]] is 2 and 2 is the max number no larger than k (k = 2).

Note:

  1. The rectangle inside the matrix must have an area > 0.
  2. What if the number of rows is much larger than the number of columns?

https://discuss.leetcode.com/topic/48875/accepted-c-codes-with-explanation-and-references

Accepted C++ codes with explanation and references

The naive solution is brute-force, which is O((mn)^2). In order to be more efficient, I tried something similar to Kadane’s algorithm. The only difference is that here we have upper bound restriction K. Here’s the easily understanding video link for the problem “find the max sum rectangle in 2D array”: Maximum Sum Rectangular Submatrix in Matrix dynamic programming/2D kadane (Trust me, it’s really easy and straightforward).

Once you are clear how to solve the above problem, the next step is to find the max sum no more than K in an array. This can be done within O(nlogn), and you can refer to this article: max subarray sum no more than k.

For the solution below, I assume that the number of rows is larger than the number of columns. Thus in general time complexity is O[min(m,n)^2 max(m,n) log(max(m,n))], space O(max(m, n)).

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
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
if (matrix.empty()) return 0;
int row = matrix.size(), col = matrix[0].size(), res = INT_MIN;
for (int l = 0; l < col; ++l) {
vector<int> sums(row, 0);
for (int r = l; r < col; ++r) {
for (int i = 0; i < row; ++i) {
sums[i] += matrix[i][r];
}

// Find the max subarray no more than K
set<int> accuSet;
accuSet.insert(0);
int curSum = 0, curMax = INT_MIN;
for (int sum : sums) {
curSum += sum;
set<int>::iterator it = accuSet.lower_bound(curSum - k);
if (it != accuSet.end()) curMax = std::max(curMax, curSum - *it);
accuSet.insert(curSum);
}
res = std::max(res, curMax);
}
}
return res;
}

https://discuss.leetcode.com/topic/49781/no-real-dp-technique-actually-used-c-critically-commented

No real DP technique actually used C++, critically commented

The last section of the solution can be tricky, but read it carefully and I believe you can get it done!

Good luck!

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
class Solution {
public:
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) //starting leftmost column;
{
vector<int> sums(rowSize, 0); //store the row pre-sums;
for(int c = l; c < colSize; ++c) //try different ending columns;
{
for(int r = 0; r < rowSize; ++r) //sum them up in rows;
sums[r] += matrix[r][c];
set<int> sums_set; //store the sums from the starting top-left;
sums_set.insert(0); //as a sentinel;
int maxSum = INT_MIN, sum = 0;
for(int i = 0; i < rowSize; ++i)
{
sum += sums[i]; //the sum from the starting top-left to current position;
auto iter = sums_set.lower_bound(sum-k); //check the possible sum candidates;
if(iter != sums_set.end()) maxSum = max(maxSum, sum-*iter); //found one, check it;
sums_set.insert(sum);
}
ret = max(ret, maxSum);
}
}
return ret;
}
};

https://discuss.leetcode.com/topic/48930/any-accepted-python-solution

Any Accepted Python Solution?

I got a TLE for the Python code below, because the time cost of bisect.insort is O(n) for a built-in list.

The code was rejudged as accepted just now, but very slow… 1800ms+

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
class Solution(object):
def maxSumSubmatrix(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
m = len(matrix)
n = len(matrix[0]) if m else 0

M = max(m, n)
N = min(m, n)
ans = None
for x in range(N):
sums = [0] * M
for y in range(x, N):
slist, num = [], 0
for z in range(M):
sums[z] += matrix[z][y] if m > n else matrix[y][z]
num += sums[z]
if num <= k: ans = max(ans, num)
i = bisect.bisect_left(slist, num - k)
if i != len(slist): ans = max(ans, num - slist[i])
bisect.insort(slist, num)
return ans or 0

Could anybody share a more efficient Python solution? Thank you :D

谢谢你,可爱的朋友。