POJ 1050 To the Max（最大字矩阵）【模板】

 题目链接：点击打开链接

 这种求最大字矩阵的题解和详解已经有很多了，我就不重复了，我的见解也是来自别人的博客。

 推荐一位博主的博客，讲的非常详细：点击打开链接  ，看懂的话做这种题就没啥问题了。

 我用的方法好的一点是比较好想，稍微一看就能明白其中原理，下面附上代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using  namespace std;
const int N=105;
int M[N][N];
int m,n,dp[N];int sum2()//求最大子段和
{int ans1=0;int s=0;for(int i=0;i<m;++i){if(s>0) s+=dp[i];else s=dp[i];if(s>ans1) ans1=s;}return ans1;
}int sum1(void)//求最大子矩阵和
{int ans=0;for(int i=0;i<m;++i){memset(dp,0,sizeof(dp));for(int j=i;j<m;++j)//求从i行到j行每列的和{for(int k=0;k<m;++k)dp[k]+=M[j][k];int sum=sum2();if(ans<sum)ans=sum;}}return ans;
}int main()
{while(~scanf("%d",&m)){for(int i=0;i<m;++i)for(int j=0;j<m;++j)scanf("%d",&M[i][j]);printf("%d\n",sum1());}return 0;
}

说实话这个方法恕我见过最简单好想的方法，没有之一，我稍微一看就懂了，自己很顺的一遍就写对了。