题目链接

算法竞赛进阶指南-39.最大的和

给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为 $1 \times 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 \times N$ 的整数数组。

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

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

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

输出格式

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

数据范围

$1 \le N \le 100$

输入样例：

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

8  0 -2

输出样例：

15

Method1 : 二维前缀和

二维前缀和模板题

预处理完二维前缀和后，前两层for循环枚举长方形的宽高，后两层for循环枚举长方形的右下角坐标,求max

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100 + 7;
const int INF = 0x3f3f3f3f;

int g[N][N];

int main() {
    memset(g, 0, sizeof g);
    
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            cin >> g[i][j];
        }
    }
    
    // 前缀和
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= n; j ++) {
            g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
        }
    }
    
    int res = -INF;
    // 枚举宽高
    for (int h = 1; h <= n; h ++) {
        for (int w = 1; w <= n; w ++) {
            // 枚举长方形的右下坐标
            for (int i = h; i <= n; i ++) {
                for (int j = w; j <= n; j ++) {
                    int cur = g[i][j] - g[i][j - w] - g[i - h][j] + g[i - h][j - w];
                    res = max(res, cur);
                }
            }
        }
    }
    
    cout << res << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度${O(n^4)}$， 其中$n^4$为四层for循环的时间复杂度。

• 空间复杂度${O(n^2)}$，空间消耗主要在$g[N][N]$。

Method2: 贪心 + DP

先枚举列的上界和下界，然后把当前的该列[上界，下界]之和看作一个数，之后可以借鉴求一维数组的最大子数组之和的DP思路，把时间复杂度优化成$O(n^3)$

#include <iostream>

using namespace std;

const int N = 100 + 7;
const int INF = 0x3f3f3f3f3f;

int g[N][N];

int main() {
    int n;
    cin >> n;
    
    for (int i = 1; i <= n ; i ++) {
        for (int j = 1; j <= n; j ++) {
            cin >> g[i][j];
            g[i][j] += g[i - 1][j];
        }
    }
    
    int res = -INF;
    for (int i = 1; i <= n; i ++) {
        for (int j = i; j <= n; j ++) {
            int last = 0;
            for (int k = 1; k <= n; k ++) {
                int cur = g[j][k] - g[i - 1][k]; 
                if (last < 0) last = cur;
                else last += cur;
                res = max(res, last);
            }
            
        }
    }
    
    cout << res << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度${O(n^3)}$， 其中$n^3$为三层for循环的时间复杂度。

• 空间复杂度${O(n^2)}$，空间消耗主要在$g[N][N]$。