直接套二维前缀和模板
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
时间复杂度:O(n^4)
#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
int a[N][N],p[N][N],n;
int main(){
cin >> n;
for(int i=0;i<n*n;i++){
cin >> a[(i/n)+1][(i%n)+1];
}
int res=-0x3f3f3f3f;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
p[i][j]=p[i][j-1]+p[i-1][j]-p[i-1][j-1] + a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int x=1;x<=i;x++){
for(int y=1;y<=j;y++){
res=max(res,p[i][j]-p[i][y-1]-p[x-1][j]+p[x-1][y-1]);
}
}
}
}
cout << res;
return 0;
}