最大子矩阵和

http://ybt.ssoier.cn:8088/problem_show.php?pid=1224

类似最大子段和

枚举矩阵的左端点i和右端点j

将每一行的i到j之间的区间和（前缀和求出）视为一个元素，求由它们构成的数列中的最大子段和

时间复杂度o(n^3)

#include<bits/stdc++.h>
using namespace std;
int a[110][110],s[110][110];
int main()
{
	memset(s,0,sizeof(s));
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	cin>>a[i][j];
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	s[i][j]=s[i][j-1]+a[i][j];
	int maxn=-100000,sum;
	for(int i=1;i<=n;i++)
	for(int j=i;j<=n;j++)
	{
		sum=0;
		for(int k=1;k<=n;k++)
		{
			sum=max(sum+s[k][j]-s[k][i-1],s[k][j]-s[k][i-1]);
			maxn=max(maxn,sum);
		}
	}
	cout<<maxn;
	return 0;
}```