问题描述
给定一个矩阵Matrix, 其中的值由正, 有负, 有0, 返回子矩阵的最大累加和.
例如: 给定矩阵
| -90 | 48 |78 |
| 64 | -40 | 64 |
| -81 | -7 | 66 |
累加和最大的子矩阵为
| 48 | 78 |
| -40| 64 |
| -7 | 66 |
问题分析
不同于数组, 矩阵需要在两个维度上进行移动, 所以逐个子矩阵尝试的方法, 复杂度很高.
一个思路是, 将矩阵的最大累加和转换为数组的最大累加和.
以矩阵
| -2 | 3 | -5 | 7 |
| 1 | 4 | -1 | -3 |
为例
1 第一行作为一个数组, 求它的最大子数组累加和 7
2 第二行作为一个数组, 求它的最大子数组累加和 5
3 将矩阵的两行数字对应相加, 得到数组 | -1 | 7 | -6 | 4 |, 求这个数组的最大累加和为7
4 求所得累加和中最大的值, 即为7.
也就是说, 在矩阵中, 限定某k行, 在必须含有k行元素的情况下, 可以通过将每一列的k个元素累加生成一个累加数组, 然后求出这个数组的最大累加和max, 就是必须含有k行元素的子矩阵中的最大累加和.
实现
class Solution
{
public:
int maxSumMatrix(std::vector<std::vector<int>>& matrix)
{
if (matrix.size() == 0 || matrix[0].size() == 0)
{
return 0;
}
int rowCount = matrix[0].size();
int max = INT_MIN;
std::vector<int> arr;
for (int startLine = 0; startLine < matrix.size(); ++startLine)
{
arr.assign(rowCount, 0);
for (int lineNum = startLine; lineNum < matrix.size(); ++lineNum)
{
for (int rowNum = 0; rowNum < rowCount; ++rowNum)
{
arr[rowNum] += matrix[lineNum][rowNum];
}
int tempMax= maxSumOfArray(arr);
max = std::max(tempMax, max);
}
}
return max;
}
private:
int maxSumOfArray(const std::vector<int>& arr)
{
int max = INT_MIN;
int cur = 0;
for (auto each : arr)
{
cur = cur + each >= 0 ? cur + each : 0;
max = cur > max ? cur : max;
}
return max;
}
};
网友评论