【已解决】面试题: 如何求出一个2维矩阵中，子矩阵最大的元素之和?

ejeker

今天被问到了这道题。这道题分为两个部分:
(1) 如何求一个数组中最大的子数组的和?
       这一问比较简单，网上都讨论的比较多了。我很快写出了程序代码。一次遍历数组就行了O(n)，空前需要N(2)

1. 
   
2. int f(int* pi,size_t num){
   
3.         int sum=0;
   
4.         int cur=0;
   
5.         for(size_t i=0;i<num;++i)
   
6.         {
   
7.                 cur+=pi[i];
   
8.                 if(cur<0)
   
9.                 {
   
10.                         cur=0;
    
11.                 }
    
12.                 if(sum<cur)
    
13.                 {
    
14.                         sum=cur;
    
15.                 }
    
16.         }
    
17.         return sum;
    
18. }
    
19. int main(int argc, char * argv[])
    
20. {
    
21.         int buf[]={2,-1,3,9,-2,1,3,-1};
    
22.         int s=f(buf,sizeof(buf)/sizeof(int));
    
23.         return 0;
    
24. }
    

复制代码

结果是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^4)的计算复杂度。既然第(1)问可以用O(n)来解决，那么本问题是否可以用O(n^2)或者更好的方式解决?

如何设计这样的一个算法?

bruceteen

例如有矩阵:
1  3 -7 9
2  7  8  2
1  9  4 -1
-3 1 -5 2

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

------------- 不对吧，如果将右边的 2, -1 也包括进来，其元素和就能增1

ejeker

bruceteen 发表于 2013-07-31 13:55
例如有矩阵:
1  3 -7 9
2  7  8 2

更正一下，第二排最后一个是-2

1  3 -7 9
2  7  8 -2

上面已经改过了。谢谢。

cjaizss

1  3 -7 9
2  7  8  2
1  9  4 -1
很显然，这个更大

ejeker

cjaizss 发表于 2013-07-31 14:18
1  3 -7 9
2  7  8  2
1  9  4 -1

嗯，我说的有失误的地方，肯定被鄙视了，汗啊。

如何找到一个最优化的算法呢?

ejeker

有个O(n^3)的算法:

枚举起始行和终止行，枚举个数一共有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)相当于算法本身保存了一部分运算的结果了。

我觉得计算的过程还可以优化一下，例如，如果我们知道了[1,2][2,3][3,4]这几个起始/终止行的组合，就能得到[1,3],[1,4],[2,4]这几个和，少了一些运算。但是我不可能这样能否就从O(n^3)降到了O(n^2)或者O(n^2 lgn)
那么，可不可能比O(n^3)更小呢?