题目翻译：

给定一个由正整数和负整数组成的二维数组，子矩形是位于数组中且大小为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。

求所给二维数组的最大子矩形。

 

一言以蔽之:降维打击。

把二维矩形每一列的和先处理出来，然后直接三重循环，ans大于0就加，小于0就舍弃之前的再加。

 

代码实现如下：

#include 
      
       using namespace std;#define rep(i, a, b) for (register int i = (a); i <= (b); i++)const int inf = 0x3f3f3f3f, maxn = 5e2 + 5;int n, max_ans = -inf;int a[maxn][maxn], sum[maxn][maxn];int MAX(int a, int b) {
    return a > b ? a : b;}int read() {    int x = 0, flag = 0;    char ch = ' ';    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();    if (ch == '-') {        flag = 1;        ch = getchar();    }    while (ch >= '0' && ch <= '9') {        x = (x << 1) + (x << 3) + ch - '0';        ch = getchar();    }    return flag ? -x : x;}void write(int x) {    if (x < 0) {        putchar('-');        x = -x;    }    if (x > 9) write(x / 10);    putchar(x % 10 + '0');}int main() {    n = read();    rep(i, 1, n)        rep(j, 1, n) {            a[i][j] = read();            sum[i][j] = sum[i - 1][j] + a[i][j];        }    rep(i, 1, n)        rep(j, i, n) {            int ans = 0;            rep(k, 1, n) {                if (ans > 0) ans += sum[j][k] - sum[i - 1][k];                else ans = sum[j][k] - sum[i - 1][k];                max_ans = MAX(ans, max_ans);            }        }          write(max_ans);    return 0;}