Aw 126. 最大的和

题目描述

给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为1 * 1或更大的连续子阵列。

矩形的总和是该矩形中所有元素的总和。

在这个问题中，具有最大和的子矩形被称为最大子矩形。

例如，下列数组：

0 -2 -7 0 
9 2 -6 2 
-4 1 -4 1 -1 8 0 -2 

其最大子矩形为：
···
9 2
-4 1 -1 8
···

数据范围

$1≤N≤100$

输入样例：

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2

输出样例：

15

算法1：

DP + 前缀和 + 枚举

此题是一个前置问题的扩展： 55. 连续子数组的最大和

如果直接使用暴力做法，需要枚举每一个子矩阵，那么需要枚举每一个起点和终点，一共四层循环，复杂的为$100^4 = 10^8$，可能会超时，而每一个子矩阵的和可以由前一个子矩阵递推而来，所以想到用DP优化。

对于一维的问题: 对每一个位置i，以i结尾的子串和的最大值由以i - 1结尾的字串最大值决定，如果前一个位置字串和最大值小于0，那么应该抛弃前面的串，只保留i，因为负数不会使求和之后值变大，由此得状态转移方程：$f[i] = max(0, f[i - 1]) + a[i]$

对于二维的问题：可以利用前缀和将二维压缩为一维，只需要枚举所有区间，在每个区间内使用一维的方法求即可，枚举区间$O(n^2)$，区间内递推$O(n)$，复杂度降为$O(n^3)$

求前缀和不需要求二维总前缀和，只需要求每一列得前缀和。

时间复杂度

$O(n^3)$

参考文献

yxc

C++ 代码

#include <iostream>

using namespace std;

const int N = 110;

int s[N][N], n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            cin >> s[i][j];
            s[i][j] += s[i - 1][j];
        }
    int res = -1e9;
    for(int i = 1; i <= n; i++)
    {
        for(int j = i; j <= n; j++)
        {
            int f = 0;
            for(int k = 1; k <= n; k++)
            {
                int v = s[j][k] - s[i - 1][k];
                if(f > 0) f = f + v;
                else f = v;

                res = max(res, f);
            }
        }
    }

    cout << res << endl;

    return 0;
}