面试题: 怎么求出一个2维矩阵中，子矩阵最大的元素之和

2013-08-04

面试题: 如何求出一个2维矩阵中，子矩阵最大的元素之和?本帖最后由 u011493015 于 2013-07-31 13:50:39 编

面试题: 如何求出一个2维矩阵中，子矩阵最大的元素之和?
本帖最后由 u011493015 于 2013-07-31 13:50:39 编辑今天被问到了这道题。这道题分为两个部分:
(1) 如何求一个数组中最大的子数组的和?
这一问比较简单，网上都讨论的比较多了。我很快写出了程序代码。一次遍历数组就行了O(n)，空前需要N(2)


int f(int* pi,size_t num){
int sum=0;
int cur=0;
for(size_t i=0;i<num;++i)
{
cur+=pi[i];
if(cur<0)
{
cur=0;
}
if(sum<cur)
{
sum=cur;
}
}
return sum;
}
int main(int argc, char * argv[])
{
int buf[]={2,-1,3,9,-2,1,3,-1};
int s=f(buf,sizeof(buf)/sizeof(int));
return 0;
}

结果是s=15

(2) 根据(1)的思路，如何求出一个2维矩阵中，子矩阵最大的元素之和?
例如有矩阵:
1  3 -7 9
2  7  8  2
1  9  4 -1
-3 1 -5 2

非常明显，元素之和最大的子矩阵是:
2 7 8
1 9 4
那么元素和是31

如何能用最佳的方法求得31呢?

显然，用穷举的方法可以，但是这需要O(n^3)的计算复杂度。既然第(1)问可以用O(n)来解决，那么本问题是否可以用O(n^2)或者更好的方式解决?

如何设计这样的一个算法?
[解决办法]
O(n^3)有，而且我知道的最好办法也就是这个复杂度。思想很简单，枚举矩形的起始行和终止行，然后做一个辅助数组A，A[i]是原数组从起始行到终止行的第i列所有数的和。然后对A做你之前发的那个线性最大。每个A本身可以用线性时间做出来。总共有O(n^2)个起始/终止行的组合。所以O(n^3)。
[解决办法]

引用:

Quote: 引用:

O(n^3)有，而且我知道的最好办法也就是这个复杂度。思想很简单，枚举矩形的起始行和终止行，然后做一个辅助数组A，A[i]是原数组从起始行到终止行的第i列所有数的和。然后对A做你之前发的那个线性最大。每个A本身可以用线性时间做出来。总共有O(n^2)个起始/终止行的组合。所以O(n^3)。

顺着你的思路，那就拿我上面给的这个矩阵来说吧:
1  3 -7 9
2  7  8  2
1  9  4 -1
-3 1 -5 2

那么枚举起始行和终止行，枚举个数一共有C(4,2)=6个。
A[0]就是原数组从起始行到终止行的第0列数组之和，那么A[0]一共有6个可能值，复杂度共O(n^2)
A[0,1]=3 第1行到第2行
A[0,2]=4 第1行到第3行
A[0,3]=1 第1行到第4行
A[0,4]=3 第2行到第3行
A[0,5]=0 第2行到第4行
A[0,6]=2 第3行到第4行

然后求出A[1]到A[5]。至此复杂度是O(n^3).
然后对于每个起始行和终止行的情况，求A的线型最大，也就是A[0,1],A[1,1],A[2,1],A[3,1],A[4,1],A[5,1]作为一个数组求一次线性最大，得到从第一行到第二行的子矩阵的最大子子矩阵元素和。

共求了N次线型最大，共花费O(n^2).
二者相加，因此最终的复杂度是O(n^3)。

之所以不用O(n^4)相当于算法本身保存了一部分运算的结果了。

那么，可不可能比O(n^3)更小呢?

问题是: 为什么这样算出来的就是我们要的结果呢?

每个起始/终止行的组合都有自己的一个A。我只是懒的打字了。其实这个数组应当标记为A[i,j,k]，然后对于A[i,j,0]~A[i,j,n-1]来做线性算法。

热点排行

软件架构设计

面试题: 怎么求出一个2维矩阵中，子矩阵最大的元素之和