矩阵最大 max sum

来源：百度知道 编辑：UC知道 时间：2024/05/14 18:22:10
给定一个2维的由正数组成的整数矩阵，找出其中具有最大和的子矩阵。一个矩阵的和就是矩阵中所有元素的和。本题中，具有最大和的子矩阵称为最大子矩阵。子矩阵是指位于整个矩阵中任何一个1×1或更大的连续的子矩阵。例如，在矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

中其最大子矩阵在其左下角：
9 2
-4 1
-1 8
提点算法，我自己的超时！-_-!!谢谢啦！

这个题目算法是三次的，类似于求最长子序列和的O(n)算法。先预处理求一个二维阵列S[i][j]=s[0][j]+s[1][j]+……+s[i][j],枚举行i和j表示第i行到第j行之间的子矩阵，然后把第k列中的i行到j行之间的元素和当成一维子矩阵和中的一个元素，用一维的O(N)算法求得i行到j行的最大子矩阵和。
这样算来，预处理是二次时间的，枚举行时间是二次的，两行间用一次最长子序列和是一次的，算来是三次时间复杂度的，就可以AC了。
给你看一下我的AC代码，在ZOJ1074上过的
#include<stdio.h>
#include<memory.h>
int a[101][100],n,i,max,sum,j,x,k;
int main()
{
scanf("%d",&n);
max=-12701;
for (i=1;i<=n;i++)
{
if (i==1)
for (j=0;j<n;j++)
{
scanf("%d",&a[1][j]);
a[0][j]=0;
}
else
for (j=0;j<n;j++)
{
scanf("%d",&x);
a[i][j]=a[i-1][j]+x;
}
}
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
{
sum=0;
for (k=0;k<n;k++)
{
sum+=(a[i][k]-a[j-1][k]);
if (sum>max) max=sum;
if (sum<0) sum=0;
}
}
printf("%d\n&qu