【错题集-编程题】最大子矩阵（二维前缀和）

一、分析题目

⼆维前缀和矩阵 的应用。

1. 初始化⼆维前缀和矩阵。
2. 枚举所有的子矩阵，求出最大子矩阵。

这道题的输入规模最大为 100，用动态规划可以做到 O(n^3)。

下面的做法虽然是暴力思路，时间复杂度为 O(n^4)，但是思路简单、代码简单。

枚举矩阵中每两两个坐标，用前缀和优化求子矩阵的过程。只要给出两个左上角，和右上角的坐标，就能求子矩阵。

• 求和：s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
• 求子矩阵(a, b, c, d)：s[c][d] - s[a-1][d] - s[c][b-1] + s[a-1][b-1];

如何枚举左右的子矩阵？

for(0 ~ n-1) -> x1

       for(0 ~ m-1) -> y1

               for(x1 ~ n-1) -> x2

                       for(y1 ~ m-1) -> y2

如何计算矩阵中所有元素的和？

二位前缀和：

1. 初始化二维 dp 表：dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]
2. 使用二维 dp 表：dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

二、代码

//值得学习的代码
#include <iostream>
using namespace std;
 
const int N = 110;
 
int n;
int dp[N][N];
 
int main()
{
    int x;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> x;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + x;
        }
    }
 
    int ret = -127 * N;
    for(int x1 = 1; x1 <= n; x1++)
    {
        for(int y1 = 1; y1 <= n; y1++)
        {
            for(int x2 = x1; x2 <= n; x2++)
            {
                for(int y2 = y1; y2 <= n; y2++)
                {
                    ret = max(ret, dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]);
                }
            }
        }
    }
 
    cout << ret << endl;
    
    return 0;
}

三、反思与改进

统计前缀和的思路是没有错的，但是在最后遍历求最大前置和子矩阵时记错了公式（应该画图的，这样就可以一眼看出错误了）。前缀和这一块的基础模板题需要再回顾一下。