更好的阅读体验

引用

官方C++题解

官方Java题解

题目描述

这一天你来到了蓝桥杯的考场，你发现考场是一个N*M的矩阵。
因为你的群友很多，你知道考场内每个人有多强，并且把实力换算成了数值。(因为有的人太弱了,所以可能出现实力值是负数的可能)
你想知道考场内实力总和最大的矩阵区域的实力和是多少。
（注意:区域是按照矩形划分的）

样例

输入格式

第一行两个整数 N M $\left(1\leq N \times M \leq 2e5\right)$
第二到N+1行是一个N*M的矩阵代表考场内的情况 $\left( -200<=实力值<=200 \right)$

输出格式

请输出考场内实力总和最大的矩阵区域的实力和是多少

输入样例 1：

3 2
8 9
10 11
-4 11

输出样例 1：

45

输入样例 2：

3 2
8 9
10 11
-12 5

输出样例 2：

38

备注

对于10%数据 $\left(1\leq N \leq M \leq 10\right)$
对于40%数据 $\left(1\leq N \leq M \leq 100\right)$
对于70%数据 $\left(1\leq N \leq M \leq 400\right)$
对于100%数据 $\left(1\leq N \times M \leq 2e5\right)$

算法

(二位前缀和) $O(nm)$

从数据范围我们可以发现要是想拿满分朴素做法是不行的，即遍历所有子矩阵。这样的话时间复杂度是 $O(n^2m^2)$ , 铁定超时。还有不要直接开全局二维数组，这样会爆段错误，具体原因暂时不清楚。我们只需要根据输入的n，m来决定数组大小就行了。

对于新的做法可以看看这个题解AcWing126.最大的和，其实就是换了一种预处理前缀和的方法，通常我们都是算这个点左上角的数的和，但是现在我们只需要算每一列的和就行了，然后枚举的时候也不需要枚举左上角的点和右下角的点，只需要枚举上下界或者左右界，再枚举每一列或者每一行即可。这题也同样可以用贪心思想

因为数据范围的问题我们可以考虑翻转数组，如果行大于列，那么我们就翻转数组，这样我们遍历的行就会变少了，大大减少了复杂度，因为上下界循环次数是n!，虽然列的遍历也增多了，但是相对而言是影响不大的

时间复杂度 $O(n)$

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

C++ 代码

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;

int main()
{
    int n , m;
    LL ans = -0x3f3f3f3f;

    scanf("%d%d", &n, &m);

    int a[n + 1][m + 1];
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            scanf("%d", &a[i][j]);

    if(n > m)
    {
        int b[m + 1][n + 1];
        // 复制数据
        for (int i = 1; i <= m; i ++ )
            for (int j = 1; j <= n; j ++ )
                b[i][j] = a[j][i];
        // 交换行列
        swap(n , m);
        // 预处理前缀和
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j++)
                b[i][j] += b[i - 1][j];
        // 枚举上下界
        for(int i = 1; i <= n; i ++)
        {
            for(int j = i; j <= n; j ++)
            {
                LL res = 0;
                for(int k = 1; k <= m; k ++)
                {
                    // 计算前k列的值，小于零就舍弃，大于就看看与ans谁大
                    res += b[j][k] - b[i - 1][k];
                    if(res < 0) res = 0;
                    if(res > ans) ans = res;   
                    // res = max(res , 0LL) + b[j][k] - b[i - 1][k];
                    // ans = max(res , ans);
                }
            }
        }
    }
    else
    {
        // 预处理前缀和
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
                a[i][j] += a[i - 1][j];
        // 枚举上下界
        for(int i = 1; i <= n; i ++)
        {
            for(int j = i; j <= n; j ++)
            {
                LL res = 0;
                for(int k = 1; k <= m; k ++)
                {
                    // 计算前k列的值，小于零就舍弃，大于就看看与ans谁大
                    res += a[j][k] - a[i-1][k];
                    if(res < 0) res = 0;
                    if(res > ans) ans = res;
                    //res = max(res , 0LL) + a[j][k]-a[i-1][k];
                    //ans = max(ans , res);
                }
            }
        }
    }
    printf("%lld\n" , ans);

    return 0;
}