蓝桥杯历届试题 最大子阵

  历届试题 最大子阵   时间限制：1.0s   内存限制：256.0MB     问题描述 　　给定一个n*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。 　　其中，A的子矩阵指在A中行和列均连续的一块。 输入格式 　　输入的第一行包含两个整数n, m，分别表示矩阵A的行数和列数。 　　接下来n行，每行m个整数，表示矩阵A。 输出格式 　　输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。 样例输入 3 3 -1 -4 3 3 4 -1 -5 -2 8 样例输出 10 样例说明 　　取最后一列，和为10。 数据规模和约定 　　对于50%的数据，1<=n, m<=50； 　　对于100%的数据，1<=n, m<=500，A中每个元素的绝对值不超过5000。   思路：二维转一维，那就是我们熟悉的最大字段之和了，当然这里并不是一下就直接整个二维表就转换成一维了， 如果有n行，那么就要枚举1 to n高度，对每个高度同一列之和用数组ans[k]储存，然后就是一维的最大字段和，具体见代码

AC代码：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=500+5; int a[maxn][maxn]; int ans[maxn]; int n,m; int Max1(){ int tol=0; int mx=ans[0]; for(int i=0;i<m;i++){ tol+=ans[i]; if(tol>mx) mx=tol; if(tol<0){ tol=0; } } return mx; } int main(){ while(scanf("%d%d",&n,&m)==2){ for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&a[i][j]); int MaxSum=a[0][0]; //初始值不能设置为0，因为可能为负 for(int i=0;i<n;i++){ memset(ans,0,sizeof(ans)); for(int j=i;j<n;j++){ for(int k=0;k<m;k++){ ans[k]+=a[j][k]; } int tmp=Max1(); if(tmp>MaxSum)MaxSum=tmp; } } printf("%d\n",MaxSum); } return 0; }

做了这道题只想说一句：革命尚未成功，同志还需努力！！！