题解 | #最大子矩阵#

#include <bits/stdc++.h>
#define MAX 100
#define INF 0x3f3f3f3f
using namespace std;


int findmax(int tmp[],int n){
	int dp[MAX];		//为了避免修改tmp的值，将tmp的值复制到dp中，对dp进行操作 
	for(int i = 1; i <= n; i++)
		dp[i] = tmp[i];
	for(int i = 2; i <= n; i++)
	{
		if(dp[i-1] > 0)
			dp[i] += dp[i-1];	
	}
	int l = dp[max_element(dp+1,dp+n+1) - dp];	//输出最大子序列和 
	return l;
}


int main(){
	int n,i,j,k,a[MAX][MAX],tmp[MAX];
	cin>>n;
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; j++)
			cin>>a[i][j];
	
	int ans = -INF;
	for(i = 1; i <= n; i++){	//上坐标行数 
		memset(tmp,0,sizeof(tmp));
		for(j = i; j <= n; j++){	//下坐标行数 
			for(k = 1; k <= n; k++)	//二维压缩成一维，将n个数复制到tmp中，后续不断累加 
				tmp[k] += a[j][k];
			int maxS = findmax(tmp,n);
			ans = max(ans,maxS);
		}
	}
	cout<<ans; 
}