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

输入格式<\text{br}>
输入中将包含一个 \text{N} \times \text{N} 的整数数组。

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

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

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

输出格式<\text{br}>
输出一个整数，代表最大子矩形的总和。

数据范围<\text{br}>
1≤\text{N}≤100

输入样例：
$``
4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2

输出样例：

15

参考答案

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 105; 
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=-9999999;


     //枚举边界1，2 
    for(int i = 1 ; i <= n ;i ++) 
    for(int j = i ; j <= n ;j++)
    {
        //枚举边界p 
        int last = 0;
        for(int k = 1; k <= n ;k ++)
        {   
            last = max(last, 0) + g[j][k] - g[i - 1][k];
            res = max(res, last);
        }
    }       

    cout<<res;

    return 0;
}


/*
数据范围
0 <N <=100 
输入样例：
4
0 -2 -7  0
9  2 -6  2
-4 1 -4  1 
-1 8  0 -2
输出样例：
15
*/ la