花两分钟静心看看，望您有所收获
题目
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 3073 通过数: 1958
【题目描述】
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1×11×1)子矩阵。
比如，如下\(4×4\)的矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
的最大子矩阵是
9 2
-4 1
-1 8
这个子矩阵的大小是1515。
【输入】
输入是一个N×NN×N的矩阵。输入的第一行给出N(0<N≤100)N(0<N≤100)。再后面的若干行中，依次(首先从左到右给出第一行的NN个整数，再从左到右给出第二行的NN个整数……)给出矩阵中的N2N2个整数，整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[−127,127][−127,127]。
【输出】
输出最大子矩阵的大小。
【输入样例】
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
【输出样例】
15
做法
暴力
我的做法就是暴力枚举，两层循环枚举矩阵左上角的坐标，再两层循环枚举右下角坐标，然后求值。
ans 就是所有值中取个max。
前缀和优化
在求矩阵和时，我们不用一个点一个点的累加，而是可以预先求出每一行的值，一行一行地累加。
这就用到了前缀和。用qian[h][i]记录第h行，从第一个元素到第i个元素的和，这样用qian[h][m] - qian[h][n - 1]就能得到第\(h\)行从第\(n\)列到第\(m\)列的值了。
注意
由于一个点可能是负的，所以ans要初始为负无穷
详注释代码
#define F(i,a,b) for(int i=a;i<=b;i++)
#define UF(i,a,b) for(int i=a;i>=b;i--)
#define INF 0x3fffffff
using namespace std;
const int N = 110;
int n, G[N][N];//G存大矩阵
int a, b, x, y;
int qian[N][N];//前缀和优化
int ans = -INF;//ans初始为负无穷
int val(int a, int b, int x, int y){//左上（a,b)右下(x,y)
int res = 0;//res用来累加矩阵和
F(i,a,x){//矩阵是第a行到第x行
res += qian[i][y] - qian[i][b - 1];//每一行是第b列到第y列
}
return res;
}
int main()
{
//输入
cin >> n;
F(i,1,n){
F(j,1,n) cin >> G[i][j];
}
//得到前缀和
F(h,1,n){
F(i,1,n){
qian[h][i] = qian[h][i - 1] + G[h][i];
}
}
//枚举左上点和右下点
F(a,1,n){
F(b,1,n){
F(x,a,n){
F(y,b,n){
ans = max(ans, val(a,b,x,y));//更新答案
}
}
}
}
//输出
cout << ans;
return 0;
}