最大子矩阵 - 贪心算法求解

最大子矩阵 - 贪心算法求解

题目描述

给定一个 $n \times n$ 的矩阵，任意选择其连续的 $a$（$0 \le a \le n$）行与 $b$（$0 \le b \le n$）列所确定的一个更小的矩阵就叫作一个子矩阵。 一个子矩阵的得分为其每个元素之和，请求出原矩阵的最大子矩阵的得分。

输入格式

从标准输入读入数据。 第一行一个正整数 $n$（$1 \le n \le 200$），代表矩阵大小。 接下来输入 $n$ 行，每行 $n$ 个整数 $a_{ij}$（$|a_{ij}| \le 100$），代表一个 $n \times n$ 的矩阵。

输出格式

输出到标准输出。 输出一个整数，代表最大子矩阵的得分。

样例 #1

样例输入 #1

3
0 3 -1
2 -1 4
-2 3 -3

样例输出 #1

7

提示

样例2

见题目目录下的 2.in 与 2.ans。

算法

(贪心) $O(n^3)$

• 暴力枚举子矩阵的上下边界，然后对每列求和，转化为一维数组，然后在一维数组中求最大子段和即可。
• 时间复杂度 $O(n^3)$。

时间复杂度

• 时间复杂度 $O(n^3)$。

空间复杂度

• 空间复杂度 $O(n)$。

C++ 代码

class Solution {
   public:
    int maxSubMatrix(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int ans = INT_MIN;
        vector<int> sum(n);
        for (int i = 0; i < n; i++) {  // 枚举上边界
            fill(sum.begin(), sum.end(), 0);
            for (int j = i; j < n; j++) {  // 枚举下边界
                int s = 0;
                for (int k = 0; k < n; k++) {  // 求和
                    sum[k] += matrix[j][k];
                    s += sum[k];
                    ans = max(ans, s);  // 求最大子段和
                    s = max(s, 0);
                }
            }
        }
        return ans;
    }
};