基准时间限制:2 秒 空间限制:131072 KB 分值: 40 难度:4级算法题
例如:3*3的矩阵:
-1 3 -1
2 -1 3
-3 1 2
和最大的子矩阵是:
3 -1
-1 3
1 2
Input
第1行:M和N,中间用空格隔开(2 <= M,N <= 500)。第2 - N + 1行:矩阵中的元素,每行M个数,中间用空格隔开。(-10^9 <= M[i] <= 10^9)
Output
输出和的最大值。如果所有数都是负数,就输出0。
Input示例
3 3-1 3 -1 2 -1 3 -3 1 2
Output示例
7
分析:
还记得有一个最大子段和问题,是一维的一组数。
最大子段和 HDU杭电acm1003
而最大子矩阵和不过是它的一个二维模式。
1、先限定其中的一维,然后另一维就可以运用最大字段和解法了。
2、不妨先限定行,行被限制在区间【i , j】上
3、在行被限定的情况下,走列就行了,用最大字段和思想
代码解释:两层外循环限定行的区间,内循环按照最大子段和走一遍即可。
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
ll arr[555][555];
ll dp[555][555];
int m,n;
int main()
{
while(~scanf("%d%d",&m,&n))
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%lld",&arr[i][j]);
dp[i][j]=dp[i-1][j]+arr[i][j];
}
}
ll ans=arr[1][1];
for(int i=1;i<=n;i++)//行上端点
for(int j=i;j<=n;j++)//行下端点
{
ll sum=0;
for(int k=1;k<=m;k++)//遍历列
{
sum+=dp[j][k]-dp[i-1][k];//第k列,i~j行的和
if(sum<0)
sum=0;
if(ans<sum)
ans=sum;
}
}
printf("%lld\n",ans);
}
return 0;
}