思路

左上角和右下角两个点可以确定一个矩形。枚举这两个点要用4个for循环 如果用二维前缀和，那么这个做法的复杂度的就是O(n^4)。

其实这个方案可以优化，那就是不枚举点。

所以我们可以利用前缀和数组表示出每个色块表示的值，然后做类似找一维数组最大连续和的操作。这样来枚举出最优矩形。

枚举边界要用3个for，复杂度为 O（n^3)

C++ 代码

#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