C++实现：寻找网格中边界元素和最大的矩形

我正在学习练习试错法，期间遇到如下算法题：

给定一个m行n列的整数网格，寻找一个边与网格边缘平行（每条边长度均大于1）的矩形，使其边界上的整数之和最大。

• 输入：第一行包含两个整数m和n；接下来m行，每行包含n个整数，描述网格的一行。
• 输出：找到的最大和。
• 约束条件：2 ≤ m, n ≤ 500；运行时间 < 3秒
  示例：
  输入：

5 4
 9 -2 -1  3
-10 -5  1 -4
 1 -1  2 -2
 3  0  0 -1
 2  2 -1  2

输出：

8

解释：边界和最大的矩形为：
1 -1 2
3 0 0
2 2 -1
其和为1 + (-1) + 2 + 0 + (-1) + 2 + 2 + 3 = 8

第三方测试用例：

5 5
0  1  0  1  0
0  0 -1  0  0
0  0  0  0  0
0  0 -4  0  0
0  1  0  2  0

初始尝试：前缀和+四层循环 #

我尝试创建数组的前缀和p[m][n]，并通过以下公式计算以(i, j)为右下角、宽w高h的矩形边界和：

sum = (p[i][j]     - p[i][j-w]   - p[i-h][j]   + p[i-h][j-w])
    - (p[i-1][j-1] - p[i][j-w+1] - p[i-h+1][j] + p[i-h+1][j-w+1])

其中(p[i][j] - p[i][j-w] - p[i-h][j] + p[i-h][j-w])计算矩形所有元素的和，(p[i-1][j-1] - p[i][j-w+1] - p[i-h+1][j] + p[i-h+1][j-w+1])计算矩形内部（不含边界）的元素和。

我用四层嵌套for循环遍历所有i、j、w、h的可能值并更新最大和，但这导致了time limit exceeded（TLE，时间超限），最初以为时间限制是1秒。

优化辅助函数但仍超时 #

根据建议，我编写了辅助函数来计算以(x0, y0)为左上角、(x1, y1)为右下角的矩形边界和，修复了部分测试用例：

int sum(int x0, int y0, int x1, int y1)
{
    if (x0 < x1 && y0 < y1)
    {
        return p[x1][y1] - p[x0][y1] - p[x1][y0] + p[x0][y0];
    }
    else if (x0 == x1 && y0 == y1)
    {
        return a[x0][y0];
    }
    else
    {
        return 0;
    }
}

int border(int x0, int y0, int x1, int y1)
{
    return sum(x0, y0, x1, y1) - sum(x0+1, y0+1, x1-1, y1-1);
}

但仍需遍历所有x0, y0, x1, y1的可能值，依然出现TLE。后来得知时间限制实际为3秒。

内容的提问来源于stack exchange，提问作者tyghn