算法思路

1. ​局部最优选择​：在每一步选择能够增加当前子矩阵和的元素。
2. ​扩展子矩阵​：尝试向四个方向（右、下、右下）扩展当前子矩阵，选择使和最大的方向。
3. ​更新最大值​：在每次扩展后，更新最大子矩阵和。

其实这道题不难，难就难在二位前缀和 表格贴这(基于数据生成器

//万物皆可dfs
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define LL long long

const int N=1e5+5;
LL s[1005][1005];
LL a[1005][1005];

int main(){
//	std::ios::sync_with_stdio(false);cin.tie(0);
	for(int i=1;i<=7;i++){
		for(int j=1;j<=7;j++){
			a[i][j]=1;
		}
	}
	for(int i=1;i<=7;i++){
		for(int j=1;j<=7;j++){
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
			printf("%5d",s[i][j]);
		}
		cout<<endl;
	}
	return 0;
}

)

公式

1. 构建 s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1];
2. 查询 s[xb][yb]-s[xa-1][yb]-s[xb][ya-1]+s[xa-1][ya-1];

话不都说，上代码

//万物皆可dfs
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define LL long long

const int N=1e5+5;
int a[1005][1005];
int s[1005][1005];
int n;
 
int main(){
	std::ios::sync_with_stdio(false);cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1];
		}
	}
	int ans=INT_MIN; 
	for(int xa=1;xa<=n;xa++){
		for(int ya=1;ya<=n;ya++){
			for(int xb=xa;xb<=n;xb++){
				for(int yb=ya;yb<=n;yb++){
					int sum=s[xb][yb]-s[xa-1][yb]-s[xb][ya-1]+s[xa-1][ya-1];
					ans=max(ans,sum);
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

严禁拷贝

谁**拷贝谁*