#include <iostream>
using namespace std;

// 定义矩阵的最大规模，这里设为 110，可根据实际情况调整
const int N = 110; 
// 二维前缀和数组，dp[i][j] 表示从矩阵左上角(1,1)到(i,j)这个矩形区域内所有元素的和
int dp[N][N];  

int main()
{
    // 输入矩阵的边长 n
    cin >> n; 
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            // 输入矩阵当前位置 (i,j) 的元素值
            cin >> x; 
            // 计算二维前缀和，公式推导：
            // dp[i][j] = 上方区域和(dp[i - 1][j]) + 左方区域和(dp[i][j - 1]) - 重复计算的左上角区域和(dp[i - 1][j - 1]) + 当前元素值(x)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + x; 
        }
    }

    // 初始化最大子矩阵和，这里用 -127 * N 是一种简单的赋初值方式，
    // 假设矩阵中元素最小可能为 -127（题目未明确说明时的一种保守处理，保证能覆盖所有可能的较小值）
    int ret = -127 * N; 
    // 枚举子矩阵的左上角坐标 (x1, y1)
    for(int x1 = 1; x1 <= n; x1++) 
        for(int y1 = 1; y1 <= n; y1++) 
            // 枚举子矩阵的右下角坐标 (x2, y2)，要求 x2 >= x1，y2 >= y1，保证子矩阵是合法的矩形区域
            for(int x2 = x1; x2 <= n; x2++) 
                for(int y2 = y1; y2 <= n; y2++) 
                {
                    // 利用二维前缀和公式计算以 (x1,y1) 为左上角，(x2,y2) 为右下角的子矩阵的和
                    // 公式解释：
                    // dp[x2][y2] 是包含该子矩阵的大矩形和；
                    // dp[x1 - 1][y2] 是子矩阵上方区域的和，需要减去；
                    // dp[x2][y1 - 1] 是子矩阵左方区域的和，需要减去；
                    // dp[x1 - 1][y1 - 1] 是上方和左方区域重复减去的部分，需要加回来。
                    int current_sum = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]; 
                    // 更新最大子矩阵和
                    ret = max(ret, current_sum); 
                }

    // 输出最大子矩阵和
    cout << ret << endl; 
    return 0;
}
  1. 二维前缀和计算：二维前缀和数组 dp 的构建是解决问题的基础。dp[i][j] 记录了从矩阵左上角 (1,1) 到 (i,j) 这个矩形区域内所有元素的累加和。通过递推公式 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + x ，可以在 \(O(n^2)\) 的时间复杂度内完成前缀和数组的计算。这样后续计算任意子矩阵的和时，就可以通过前缀和快速推导，无需重复遍历子矩阵元素求和。
  2. 枚举子矩阵：代码通过四层循环枚举所有可能的子矩阵。外层两层循环 x1 和 y1 确定子矩阵的左上角坐标，内层两层循环 x2 和 y2 确定子矩阵的右下角坐标，并且通过 x2 >= x1 、y2 >= y1 的限制，确保枚举的是合法的、连续的矩形区域。
  3. 子矩阵和计算与更新最大值：对于每一个枚举到的子矩阵，利用预先计算好的二维前缀和数组，通过公式 dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] 快速计算出该子矩阵的和。然后将这个和与当前记录的最大和 ret 比较，如果更大就更新 ret 。最终 ret 中保存的就是整个二维矩阵中所有可能子矩阵和的最大值。