最大子矩阵

解题思路:二维前缀和

注意事项:

参考代码:

#include<iostream>
#include<algorithm> 
#include<utility>
using namespace std;
const int N = 1e2 + 10;
int a[N][N],s[N][N],mx;
int main()
{
	int n , x; 
	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 - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= n; j ++)
			for(int k = i; k <= n; k ++)
				for(int l = j; l <= n; l ++)
					if( mx < s[k][l] + s[i-1][j-1] - s[i - 1][l] - s[k][j-1]) mx = s[k][l] + s[i-1][j-1] - s[i - 1][l] - s[k][j-1];				
	cout << mx;	
	return 0;
}