题目链接
很经典的一道题
最大子矩阵是最大字段和在二维中的扩展，首先需要对整个矩阵进行降维处理， i i i表示起始行, j j j表示终止行，将 i − j i-j i−j之间的行，对应的行求和，形成一个一维数组，然后在该数组中求最大子段和， i i i和 j j j遍历 m m m行，故时间复杂度为 O ( n 3 ) O(n^3) O(n3),最大值在计算过程中顺带标记并输出。

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=105;
int arr[maxn][maxn], sum[maxn],dp[maxn],matrix[maxn][maxn];
int main(){
	int n,ans=-1;
	while(cin>>n){
		memset(matrix,0,sizeof(matrix));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				cin>>arr[i][j];
			} 
		}
		
		for(int i=1; i<=n; i++){  //前缀和
			for(int j=1;j<=n; j++){
			   matrix[i][j] = matrix[i-1][j] + arr[i][j];
			}
		}
		int area;
		for(int i=1;i<=n;i++){
			for(int j=i;j<=n;j++){
				area=0;
				for(int k=1;k<=n;k++){  //sum中为一维最大连续子数组和
					sum[k] = matrix[j][k] - matrix[i-1][k];
				}
				for(int k=1;k<=n;k++){  //用dp的思路求最大连续子数组和的最大值
					dp[k] = max(sum[k]+dp[k-1], sum[k]);
					if(dp[k] > ans) ans = dp[k];
				}
			}
		}
		cout<<ans<<endl;	
	}
	
	
	return 0;
}