问题陈述
给定一个m x n矩阵matrix和一个整数k，返回矩阵中矩形的最大总和，以使其总和不大于k 。。
保证将有一个矩形，总和不超过k。
从：https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k。
提取的问题声明示例1：
Input: matrix = [[1, 0, 1], [0, -2, 3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).
示例2：
Input: matrix = [[2, 2, -1]], k = 3
Output: 3
约束：
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -100 <= matrix[i][j] <= 100
- -10^5 <= k <= 10^5
跟进：如果行的数量比列数大得多？
解决方案
方法1：蛮力
幼稚的方法是检查输入矩阵中的所有可能的子膜片，以计算不大于K的矩形的最大总和。对于每个子矩阵，我们检查其元素的总和是否小于或不等于K。 。我们存储了不超过k的子正确的总和并返回答案。
这种方法的C ++解决方案如下：
class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int m = matrix.size();
int n = matrix[0].size();
int result = numeric_limits<int>::min();
vector<vector<vector<vector<int>>>> computeSum(
m,
vector<vector<vector<int>>>(
n,
vector<vector<int>>(
m,
vector<int>(n, 0)
)
)
);
for (int rowLength = 0; rowLength < m; ++ rowLength) {
for (int columnLength = 0; columnLength < n; ++columnLength) {
for (int i = 0; i + rowLength < m; ++i) {
for (int j = 0; j + columnLength < n; ++j) {
if (rowLength == 0 && columnLength == 0) {
computeSum[i][j][i + rowLength][j + columnLength] =
matrix[i][j];
} else if (rowLength == 0) {
computeSum[i][j][i + rowLength][j + columnLength] =
computeSum[i][j][i + rowLength][j + columnLength - 1]
+
matrix[i + rowLength][j + columnLength];
} else if (columnLength == 0) {
computeSum[i][j][i + rowLength][j + columnLength] =
computeSum[i][j][i + rowLength - 1][j + columnLength]
+
matrix[i + rowLength][j + columnLength];
} else {
computeSum[i][j][i + rowLength][j + columnLength] =
computeSum[i][j][i + rowLength - 1][j + columnLength]
+
computeSum[i][j][i + rowLength][j + columnLength - 1]
-
computeSum[i][j][i + rowLength - 1][j + columnLength - 1]
+
matrix[i + rowLength][j + columnLength];
}
if (computeSum[i][j][i + rowLength][j + columnLength] == k) {
return k;
} else if (computeSum[i][j][i + rowLength][j + columnLength] < k) {
result = max(
result,
computeSum[i][j][i + rowLength][j + columnLength]
);
}
}
}
}
}
return result;
}
};
这种方法的时间复杂性为 o（n ^ 4）。该解决方案将超出一个巨大的矩阵，这不是最佳方法。
方法2：Kanade算法
我们可以使用Kanade算法的概念来优化蛮力方法。 kadane的算法在 o（n）时间的一维阵列中找到了一个最大总和连续的子阵列。使用此概念，我们将创建一个整数数组，该整数数组存储每个行的前缀总和，从i到j，其中 0 。我们将在每个此类数组上运行kadane的算法，以使最大可能的总和与任何子阵列的最接近 k ，就像我们在方法1中相同的方式。
。请参阅此帖子Maximum Subarray，以了解 Kanade算法。
让我们检查算法。
算法
// maxSumSubmatrix(matrix, k)
- set m = matrix.length
n = matrix[0].length
result = INT_MIN
- loop for i = 0; i < n; i++
// initialize sum of size m with all values in it as 0
- vector<int> sum(m, 0)
- loop for j = i; j < n; j++
- loop for r = 0; r < m; r++
- update sum[r] = sum[r] + matrix[r][j]
- for end
- for end
- set result = max(result, computeMaxSubarraySum(sum, k))
- for end
- return result
// computeMaxSubarraySum(sum, k)
- set currentSum = 0
maxSum = INT_MIN
- create set sumValues and insert the value 0
set<int> sumValues
sumValues.insert(0)
- loop for i = 0; i < sum.size; i++
- update currentSum = currentSum + x
- set auto it = sumValues.lower_bound(currentSum - k)
- if it != sumValues.end()
- update maxSum = max(maxSum, currentSum - *it)
- if end
- sumValues.insert(currentSum)
- for end
- return maxSum
这种方法的时间复杂性为 o（m * n ^ 2 * log（m））。其中m是行的数量，而n是输入矩阵中的列数。空间复杂性是 o（n）。
让我们在 c ++ ， golang 和 javascript 中查看我们的解决方案。
。C ++解决方案
class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
int result = INT_MIN;
for(int i = 0; i < n; i++) {
vector<int> sum(m, 0);
for(int j = i; j < n; j++) {
for(int r = 0; r < m; r++) {
sum[r] += matrix[r][j];
}
result = max(result, computeMaxSubarraySum(sum, k));
}
}
return result;
}
int computeMaxSubarraySum(vector<int> sum, int k) {
int currentSum = 0;
int maxSum = INT_MIN;
set<int> sumValues;
sumValues.insert(0);
for(auto x: sum) {
currentSum += x;
auto it = sumValues.lower_bound(currentSum - k);
if (it != sumValues.end()) {
maxSum = max(maxSum, currentSum - *it);
}
sumValues.insert(currentSum);
}
return maxSum;
}
};
去解决方案
func maxSumSubmatrix(matrix [][]int, k int) int {
m, n := len(matrix), len(matrix[0])
sum := make([]int, n)
sumValues := make(sortedIntSet, n)
result := math.MinInt32
for startRow := range matrix {
for i := range sum {
sum[i] = 0
}
for row := startRow; row < m; row++ {
for col, val := range matrix[row] {
sum[col] += val
}
currentSum := 0
maxSum := sum[0]
for _, val := range sum {
currentSum = max(currentSum + val, val)
maxSum = max(maxSum, currentSum)
}
if maxSum <= k {
result = max(result, maxSum)
continue
}
currentSum = 0
sumValues = sumValues[:1]
sumValues[0] = 0
for _, val := range sum {
currentSum += val
partnerIdx := sort.SearchInts(sumValues, currentSum-k)
if partnerIdx != len(sumValues) {
result = max(result, currentSum - sumValues[partnerIdx])
}
sumValues.insert(currentSum)
}
}
}
return result
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
type sortedIntSet []int
func (s *sortedIntSet) insert(x int) {
i := sort.SearchInts(*s, x)
if i == len(*s) {
*s = append(*s, x)
} else if (*s)[i] != x {
*s = append(*s, 0)
copy((*s)[i+1:], (*s)[i:])
(*s)[i] = x
}
}
JavaScript解决方案
/**
* @param {number[][]} matrix
* @param {number} k
* @return {number}
*/
var maxSumSubmatrix = function(matrix, k) {
let m = matrix.length, n = matrix[0].length;
let result = Number.MIN_VALUE;
for(let i = 0; i < n; i++) {
let sum = new Array(m).fill(0);
for(let j = i; j < n; j++) {
for(let r = 0; r < m; r++) {
sum[r] += matrix[r][j];
}
result = Math.max(result, computeMaxSubarraySum(sum, k));
}
}
return result;
};
var computeMaxSubarraySum = function(sum, k) {
let currentSum = 0;
let maxSum = Number.MIN_VALUE;
let sumValues = new Set();
sumValues.add(0);
for(let r = 0; r < sum.length; r++) {
currentSum += sum[r];
let list = Array.from(sumValues);
let it = list.lastIndexOf(currentSum - k)
if (it > -1) {
maxSum = Math.max(maxSum, currentSum - it);
}
sumValues.add(currentSum);
}
return maxSum;
};
干式运行
让我们干燥运行算法以了解解决方案的工作原理。
Input: matrix = [[1, 0, 1], [0, -2, 3]]
k = 2
// maxSumSubmatrix(matrix, k)
Step 1: m = matrix.size()
= 2
n = matrix[0].size()
= 3
result = INT_MIN
Step 2: loop for i = 0; i < n
0 < 3
true
vector<int> sum(m, 0)
sum = [0, 0]
loop for j = i; j < n; j++
loop for r = 0; r < m; r++
sum[r] = sum[r] + matrix[r][j]
for end
for end
so after the above loop
sum = [1, 0]
result = max(result, computeMaxSubarraySum(sum, k))
// computeMaxSubarraySum(sum, 2)
// computeMaxSubarraySum([1, 0], 2)
Step 3: set currentSum = 0
maxSum = INT_MIN
set<int> sumValues
sumValues.insert(0)
loop for auto x: sum
currentSum = currentSum + x
= 0 + 1
= 1
sumValues = [0]
it = sumValues.lower_bound(currentSum - k)
= sumValues.lower_bound(1 - 2)
= sumValues.lower_bound(-1)
= -1
sumValues.add(currentSum)
sumValues.add(1)
sumValues = [0, 1]
loop for auto x: sum
currentSum = currentSum + x
= 1 + 0
= 1
sumValues = [0, 1]
it = sumValues.lower_bound(currentSum - k)
= sumValues.lower_bound(1 - 2)
= sumValues.lower_bound(-1)
= -1
Step 4: return maxSum
return INT_MIN
// maxSumSubmatrix(matrix, k)
Step 5: result = max(result, computeMaxSubarraySum(sum, k))
= max(INT_MIN, INT_MIN)
= INT_MIN
i++
i = 1
Step 6: loop for i < n
1 < 3
true
vector<int> sum(m, 0)
sum = [0, 0]
loop for j = i; j < n; j++
loop for r = 0; r < m; r++
sum[r] = sum[r] + matrix[r][j]
for end
for end
so after the above loop
sum = [0, -2]
result = max(result, computeMaxSubarraySum(sum, k))
We compute the same steps for the whole matrix.
We return the result, and the answer is 2.