KY63 最大子矩阵

二维前缀和板子
ti

#include<bits/stdc++.h>

using namespace std;

int n;
int t;
int sum[105][105];

int Sum(int x, int y){  //求矩阵和 
	int t = -1e8;
	for(int i = x; i <= n; i ++ ){
		for(int j = y; j <= n; j ++ ){
			int op = sum[i][j] - sum[x - 1][j] - sum[i][y - 1] + sum[x - 1][y - 1];
			t = max(op, t);
		}
	}
	return t;
} 

int main()
{
	while(cin>>n){
		memset(sum, 0, sizeof(sum));
		for(int i = 1; i <= n; i ++ ){
			for(int j = 1; j <= n; j ++ ){
				cin>>t;
				sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + t;
			}
		}
		int ans = -1e8;
		for(int i = 1; i <= n; i ++ ){  
			for(int j = 1; j <= n; j ++ ){ 
				ans = max(ans, Sum(i, j));
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}