使用二維前綴和數組求解
設pre[i][j]為二維數組f第1行第1列到第i行第j列矩形區域內的元素和
即左上角元素為f[0][0]、右下角元素為f[i-1][j-1]的矩形元素和
根據容斥原理，有f[i-1][j-1] = pre[i][j] - pre[i-1][j]- pre[i][j-1] + pre[i-1][j-1]
由此可根據如下遞推關系，先得到整個二維前綴和數組pre：
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] - f[i-1][j-1]
有了pre，只要給出左上角坐標(a,b)和右下角坐標(c,d)，就可以快速求出該矩形內元素和：
sum = pre[c][d] - pre[c][b-1] - pre[a-1][d] + pre[a-1][b-1]
C語言代碼和運行結果如下：
輸出符合示例，望采納~
附源碼：
#include <stdio.h>
int f[1000][1000], pre[1001][1001]; // pre為二維前綴和數組
int main() {
int n, i, j, max = -1e8; // -100*1000*1000，最大值初始化為可能的最小值
int m, a, b, c, d, sum;
scanf("%d", &n);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
scanf("%d", &f[i][j]);
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) { // 容斥原理得前綴和遞推公式
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + f[i-1][j-1];
}
}
scanf("%d", &m);
while (m--) {
scanf("%d %d %d %d", &a, &b, &c, &d);
sum = pre[c][d] - pre[c][b-1] - pre[a-1][d] + pre[a-1][b-1];
if (sum > max) max = sum;
}
printf("%d\n", max);
return 0;
}