题目网址

暴力枚举

#include<bits/stdc++.h>
using namespace std;
const int N =  1e3+10;
int a[N][N],sum=-99999999;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	for(int x1=1;x1<=n;x1++){
		for(int y1=1;y1<=n;y1++){
			for(int x2=x1;x2<=n;x2++){
				for(int y2=y1;y2<=n;y2++){
					int s=0;
					for(int i = x1;i<=x2;i++){
						for(int j = y1;j<=y2;j++){
							s+=a[i][j];
						}
					}
					if(s>sum)sum=s;
				}
			}
		}
	}
	cout<<sum;
	return 0;
}

最大子矩阵和-暴力-前缀和优化

#include<bits/stdc++.h>
using namespace std;
const int N =  1e3+10;
int a[N][N],b[N][N],sum=-99999999;
int main(){
	int n;
	cin>>n;//输入
	for(int i=1;i<=n;i++){//输入的二维数组的行
		for(int j=1;j<=n;j++){//输入的二维数组的列
			cin>>a[i][j];//输入二维数组的单个元素
			b[i][j]=a[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
		}
	}
	for(int x1=1;x1<=n;x1++){
		for(int y1=1;y1<=n;y1++){
			for(int x2=x1;x2<=n;x2++){
				for(int y2=y1;y2<=n;y2++){
					int s=0;
					s = b[x2][y2]-b[x2][y1-1]-b[x1-1][y2]+b[x1-1][y1-1];
					if(s>sum)sum=s;
				}
			}
		}
	}
	cout<<sum;
	return 0;
}

最大子矩阵和-dp

#include<bits/stdc++.h>
using namespace std;
const int N =  1e3+10;
int a[N][N],d[N],sum=-99999999;
int main(){
	int n;// 矩阵的大小
	cin>>n;
	for(int i=1;i<=n;i++){//输入的二维数组的行
		for(int j=1;j<=n;j++){//输入的二维数组的列
			cin>>a[i][j];//输入二维数组的单个元素
			a[i][j]+=a[i][j-1];//让a[i][j]保存每一行前j个元素之和，二维数字的下标从1开始，a[i][0]=0
		}
	}
	// l 和 r是代表什么？
	// l和r代表以l列开始r列结束的所有子矩阵
	// d数组是干什么用的？
    // d[i]是l和r代表以l列开始r列结束的所有子矩阵，以i行开头的最大子矩阵
	
	for(int l=1;l<=n;l++){//遍历起始列l
		for(int r=l;r<=n;r++){//终止列r
			int s=-9999999;//l和r代表以l列开始r列结束的所有子矩阵,最大值擂台
			for(int i=n;i>=1;i--){//遍历行，
				if(d[i+1]<=0)d[i]=a[i][r]-a[i][l-1];
				//如果以d[i+1]<=0,代表以i+1为起点的最大子矩阵是划不来的
				//d[i]赋值为第i行自己组成子矩阵和
				else d[i]=a[i][r]-a[i][l-1]+d[i+1];
				//如果以d[i+1]>0,代表以i+1为起点的最大子矩阵是有价值的
				//d[i]赋值为第i行自己组成子矩阵和+i+1为起点的最大子矩阵和
				if(d[i]>s)s=d[i];
				// 擂台法，每行做起点的最大子矩阵和的最大值
				// s保存的是：l和r代表以l列开始r列结束的所有子矩阵的最大子矩阵和
			}
			if(s>sum)sum=s;
			// sum保存所有子矩阵的最大子矩阵
		}
	}
	cout<<sum;
	return 0;
}