[leetcode]363. Max Sum of Rectangle No Larger Than K
タイトルリンク:https://leetcode.com/problems/max-sum-of-sub-matrix-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.
Example:
The answer is
Note: The rectangle inside the matrix must have an area > 0. What if the number of rows is much larger than the number of columns?
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.
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:
class Solution {
public:
int maxSumSubmatrix(vector>& 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 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 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;
}
};