更好的阅读体验

扩展题

“九韶杯”河科院程序设计协会第一届程序设计竞赛G.最强对手矩阵

引用

贪心思想可以看看秦同学的题解，大佬还是一如既往的厉害，我还是依然很菜。在这里就不画图了，可以看看以下大佬画的图

秦淮岸灯火阑珊 AcWing 126. 最大的和

Bug-Free AcWing 126. 最大的和

Aniway AcWing 126. 最大的和

皮皮柯 AcWing 126. 最大的和(连续子序列和dp求解）

题目描述

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

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

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

例如，下列数组：

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

其最大子矩形为：

9 2 
-4 1 
-1 8

它拥有最大和 15。

样例

输入格式

输入中将包含一个 N×N 的整数数组。

第一行只输入一个整数 N，表示方形二维数组的大小。

从第二行开始，输入由空格和换行符隔开的 N2 个整数，它们即为二维数组中的 N2 个元素，输入顺序从二维数组的第一行开始向下逐行输入，同一行数据从左向右逐个输入。

数组中的数字会保持在 [−127,127] 的范围内。

输出格式

输出一个整数，代表最大子矩形的总和。

数据范围

$1≤N≤100$

输入样例 1：

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

8  0 -2

输出样例 1：

15

算法

(二位前缀和) $O(n^2)$

这题的数据范围很小，所以我们直接遍历所有子矩阵就行了，但是这样做复杂度是很高的，虽然不会超时，但是在这里介绍一个更好的思路。可以减少一层循环。我们预处理前缀和的时候，只计算列方向的前缀和或者行方向的前缀和。这样遍历的时候我们只要遍历上下界，即矩阵的上下边或者左右边就行了，然后算一下前k列或前k行的最大值。

这题也有一点点贪心的影子，如果前几列加上这一列比零还小，那么我们就直接舍去，因为这个子矩阵的话，我们还不如选剩下的矩阵，因为加上这个矩阵只会更小

多说不益，我们来试试吧

时间复杂度 $O(n^2m)$

预处理前缀和数组，所以计算的时候是 $O(1)$ 的

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int a[N][N];

int n;
int maxx = -0x3f3f3f3f;

int main()
{
    cin >> n;
    // 读入数据
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            cin >> a[i][j];
    // 预处理前缀和
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            a[i][j] += a[i - 1][j];
    // 遍历上下界
    for(int i = 1; i <= n; i ++)
    {
        for(int j = i; j <= n; j ++)
        {
            // 存每一个上下界的前k列的值
            int t = 0;
            for(int k = 1; k <= n; k ++)
            {
                // 计算前k列，如果上一个t小于零就不要了
                t = max(t , 0) + a[j][k] - a[i - 1][k];
                maxx = max(maxx , t);
            }
        }
    }

    cout << maxx << endl;

    return 0;
}