传送门

思路

二维矩阵求区间最大元素和可以通过列方向上的前缀和来实现压缩矩阵以降维，时间复杂度降级。

代码

#include
using namespace std;
int Array[125][125], dp[125], n, ans;
int main(void)
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> Array[i][j];
    for (int col = 1; col <= n; col++)
        for (int row = 1; row <= n; row++)
            Array[row][col] += Array[row - 1][col];
    for(int i=1;i<=n;i++)
    {
        for (int k = 1; k <= i; k++)
        {
            for (int j = 1; j <= n; j++)
            {
                int gap = Array[i][j] - Array[i - k][j];
                dp[j] = max(dp[j - 1] + gap, gap);
                ans = max(dp[j], ans);
            }
        }
    }
    cout << ans;
    return 0;
}