题目链接
题意：从一个二维矩阵中选出一个子矩阵使得和最大。由于数据比较小，我们可以枚举行开始的位置和行结束的位置，然后对于选中的行求列的前缀和，然后再按一维求最大子序列的方法解决。
#include<bits/stdc++.h> using namespace std; const int maxn=507; int n,m; int ans; int a[maxn][maxn],dp[maxn],b[maxn]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); ans=-1000000; for(int s=1;s<=n;s++) //枚举行开始的位置 { memset(b,0,sizeof(b)); for(int e=s;e<=n;e++) //枚举行开始的位置到行结束的位置 { for(int i=1;i<=m;i++) { b[i]+=a[e][i]; //计算选中的行的列的前缀和 } dp[1]=b[1]; for(int i=2;i<=m;i++) { if(dp[i-1]<0) dp[i]=b[i]; else dp[i]=dp[i-1]+b[i]; if(dp[i]>ans) ans=dp[i]; } } } printf("%d\n",ans); return 0; }