算法刷题目数组和矩阵
Source
Edit
History

子矩阵的最大累加和

子矩阵的最大累加和

一、题目

给定一个矩阵，这个矩阵中的值有正、负、0。返回子矩阵的最大累加和。如下例子

1
2
3
4
5
matrix{{-90, 48, 78}, {64, -40, 64}, {-81, -7, 66}};
返回 209，子矩阵如下：
48   78
-40  64
64   66

二、思路

首先我们先看一个矩阵都有哪些子矩阵。假设一个 3 行的矩阵，我们先不管列，暂止列的数据全部用上，那么有这么多子矩阵

  • 只有第一行的子矩阵；只有第二行的子矩阵；只有第三行的子矩阵
  • 第一行 + 第二行的子矩阵；第二行 + 第三行的子矩阵
  • 第一行 + 第二行 + 第三行的子矩阵

如果得到了这些子矩阵，将所有子矩阵的所有列都累加起来，成为一个只有一行的数组。然后转换成求子数组的最大累加和。所有子矩阵中，组成的所有的子数组，即可求得最大累加和。

本题目就是首先将子矩阵转换为数组，然后求数组的子数组的最大累加和。

三、代码

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
31
32
33
34
#include <vector>
#include <iostream>

class Solution {
public:
    int get_max_sum(const std::vector<std::vector<int>>& matrix) {
        if (matrix.empty()) {
            return 0;
        }
        int max = 0;
        int cur = 0;
        for (int i = 0; i < matrix.size(); ++i) {
            std::vector<int> sum_arr(matrix[0].size(), 0);
            for (int j = 0; j < matrix.size(); ++j) {
                cur = 0;
                for (int k = 0; k < sum_arr.size(); ++k) {
                    sum_arr[k] += matrix[j][k];
                    cur += sum_arr[k];
                    max = std::max(max, cur);
                    cur = cur < 0 ? 0 : cur;
                }
            }
        }
        return max;
    }
};

int main() {
    Solution s;
    std::vector<std::vector<int>> matrix{{-90, 48, 78}, {64, -40, 64}, {-81, -7, 66}};
    auto res = s.get_max_sum(matrix);
    std::cout << res << std::endl;
    return 0;
}

假定矩阵的行长度为 N，列长度为 M。 时间复杂度：O(N*M*N)，额外的空间复杂度：O(M)