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

(最大连续子序列求和dp来求解这个问题) $O(n^3)$

我们假设把每一行和看做一个新的元素 那么就从0到n枚举一下当前是在哪一行 比如0到1行和看做一个元素
那么我当前就在第1行 0到3行和看做一个元素 那么我就在第3行 注意是和 我们就固定了右区间了 然后枚举左区间 左区间从0到i-1枚举 比如我固定是3 那么我就枚举区间 (0 3) (1 3) (2 3) 这样求这个区间里面的连续子序列和 每次更新一下答案就好了

枚举区间两个for循环 区间里面一个for循环求dp值 复杂度为o(n^3)

代码如下

c++代码如下

`
 #include<bits/stdc++.h>

using namespace std;

int a[102][102],sum[102][102],dp[102];

int main()
{
    int n;
    cin>>n;
    memset(sum,0,sizeof(sum));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin>>a[i][j];
            sum[i][j] = sum[i][j-1] + a[i][j];// 每一行都当做一个元素
        }
        //puts("");
    }
    int ans = -1000;
    for(int j = 1; j <= n ; j++)
    {
        for(int k = 0; k < j; k++)// 这两个for循环枚举区间的
        {
            for(int p = 0; p < 102 ; p++) dp[p] = -1000;// 每次dp都需要初始化
            dp[0] = 0;
            for(int i = 1; i <= n; i++)// dp求和
            {
                dp[i] = max(sum[i][j] - sum[i][k],dp[i-1] + sum[i][j] - sum[i][k]);
                ans = max(ans,dp[i]);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}