本题是对一维最大和子区间的推广,思路为穷举上下边界,利用前缀和数组初始化列上和,此时已经转换为了一维问题,然后穷举右边界即可.
时间复杂度为O(n^3);

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 105;
int n,ans = -1e5;//n*n的矩阵
int arr[N][N];
int main() {
    cin >> n;
    /*
    初始化列的前缀和
    */
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> arr[i][j];
            arr[i][j] += arr[i - 1][j];
        }
    }
    /*
    枚举上底和下底的位置
    */
    for (int i = 1;i <= n;i++) {
        for (int j = i;j <= n;j++) {
            /*
            **last表示当前计算得到的矩形和的最大值,假设当前计算得到的矩形和大于0,那么在下一次就可以加上这一次的和得到更大的;
            反之,就不加上上一次计算的和,而只得到大小为1 * (j - i + 1)矩形的值.
            即递推公式:
                f(i) = 
                    f(i - 1) + a[i];    若f(i - 1) > 0
                    a[i];   若f(i - 1) <= 0.**
            */
            int last = 0;
            //枚举右边界的位置,效仿一维数组时的做法
            for (int k = 1;k <= n;k++) {
                last = max(last,0) + arr[j][k] - arr[i - 1][k];
                ans = max(last,ans);
            }
        }
    }
    cout << ans << endl;
    return 0;
}