思路
一道比较经典的题目。
首先我们可以把方阵扩展一下，变成 \(4n^2\) 大小的方阵。
问题就变为在长度为 \(2\times n\) 的方阵中求一个长和宽均小于等于 \(n\) 的子矩阵的和的最大值。
方法一：预处理矩阵的二维前缀和，暴力枚举子矩阵的左上角和右下角并统计答案 时间复杂度 \(O(n^4)\) ，因为其他题解均有阐述，这里不再详细介绍。
方法二：我们可以只枚举矩形的上下边界，用其他方法来确定左右边界。
因为上下边界已经确定，我们可以把它压缩成一维的数组，问题就会变成最大子段和问题，这不是单调队列的拿手好戏吗？
设 \(f_i\) 为以 \(i\) 结尾的最大子段和，有方程： \(f_i = \max(sum_i - sum_j)(i- n\le j < i)\)。
即
\[f_i=sum_i-\min(sum_j)(i- n\le j < i) \]用单调队列可以轻松维护，时间复杂度 \(O(n^3)\) 。
\(Code\)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
const int N = 200 << 1;
int a[N][N];
int n, T;
int sum[N];
int f[N<<1];
int que[N<<1], Front, Back;
int s[N];
int dp(int *h){//单调队列求最大子段和
int ans;
Front = 1, Back = 1;
que[1] = 1;ans = f[1] = s[1] = h[1];
for(int i = 2; i <= n; i ++){
s[i] = s[i - 1] + h[i];
while(Front <= Back and i - que[Front] > n/2)Front ++;
f[i] = s[i] - s[que[Front]];
ans = max(ans, f[i]);
while(Front <= Back and s[que[Back]] >= s[i])Back--;
que[++Back] = i;
}
return ans;
}
int main(){
// freopen("text.in", "r", stdin);
// freopen("text.out", "w", stdout);
scanf("%d", &T);
while(T--){
int ans = -0x3f3f3f3f;
scanf("%d", &n);
//把矩阵括大两倍
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
scanf("%d", &a[i][j]), a[i][j + n] = a[i][j],
a[i + n][j] = a[i + n][j + n] = a[i][j];
n <<= 1;
for(int i = 1; i <= n; i ++){
memset(sum, 0, sizeof sum);
for(int j = i; j <= n and j - i + 1 <= n / 2; j ++){
for(int k = 1; k <= n; k ++)
sum[k] += a[j][k];//压缩，可以由 [i, j - 1]递推得到
ans = max(ans, dp(sum));
}
}
printf("%d\n", ans);
}
return 0;
}