面试趣题：求不连续子数组最大和的值

holly2008

《编程之美》一书上有一道题：给定一个由N个整数元素组成数组a，写一个函数在其中找出连续子数组和的最大值。例如给定数组为{1, -2, 3, 5, -1, 2}，则和最大的连续子数组是{3, 5, -1, 2}，函数返回值是9。

这是一道典型的动态规划问题，书中循序渐进地通过分析给出了一个时间复杂度为O(N)空间复杂度为O(1)的最优解。我在面试时碰到了这道题的一道有趣变体，即同样给定一个数组，写一个在其中找出不连续子数组和的最大值，也就是说子数组里的任意相邻的两个元素，在原数组里都必须是不相邻的才行。同样以数组{1, -2, 3, 5, -1, 2}为例，则和最大的不连续子数组是{1, 5, 2}，函数返回值是8。

显然，最直接的思路我们可以采用穷举法，对于此类寻找符合条件的子数组的问题，无非就是对原数组上每位元素是否属于子数组做一次遍历判断。由于每位元素都有属于和不属于子数组两种可能性，那么穷举的时间复杂度为O(2^N)。即使考虑“不连续”这个限制条件，即某位元素被选中属于子数组后，则其相邻元素就一定不能被选中，也对时间复杂度的数量级不会有太多影响。因此很明显，这绝对是个愚蠢的答案……

从《编程之美》一题中得到启发，我们是不是也可以用动态规划的方法来解这道题呢？假设从原数组a第i位开始的最大不连续子数组和为m[ i ]，那么它的值有两种可能，一种是当前元素a[ i ]与隔一位上子问题解m[ i+2 ]之和（由不连续性质决定），另一种是不包含当前元素而直接等于前一位上子问题解m[ i+1 ]，那么我们可以写出递推公式为：m[ i ] = max(a[ i ] + m[ i+2 ], m[ i+1 ])。

等等，也许你要说，好像这个递推式有漏洞啊，因为前一位上的解m[ i+1 ]本身就有可能是包含或不包含a[ i+1 ]，假如m[ i+1 ]不包含a[ i+1 ]，那么岂不是还要考虑a[ i ]+m[ i+1 ]这种可能性呢？

这个递推式真的经不起推敲吗？我们不妨重新整理一下思路：由于原数组上每一元素都有取与不取两种可能，那么也就对应有包含和不包含该元素的两个子数组的最大和。对于原数组a中第i位上的元素，假设包含a[ i ]元素的子数组最大和为s[ i ]，而不包含元素a[ i ]的子数组最大和为ns[ i ]，因此所要求的不连续子数组最大和m[ i ] = max(s[ i ], ns[ i ])。那么根据题意我们可以整理出递推关系如下：

   s[ i ] = max(a[ i ] + ns[ i+1 ], a[ i ] + m[ i+2 ])
    ns[ i ] = m[ i+1 ]
    m[ i ] = max(a[ i ] + ns[ i+1 ], a[ i ] + m[ i+2 ], m[ i+1 ])

有趣的地方在于ns[ i ] = m[ i+1 ]这一项上，根据它我们可以得到ns[ i+1 ] = m(i+2)，也就是说假如m[ i+1 ]不包含a[ i+1 ]的话，那么它一定等于m[ i+2 ]，所以a[ i ]+ns[ i+1 ]等价于a[ i ] + m[ i+2 ]，递推式m[ i ] = max(a[ i ] + m[ i+2 ], m[ i+1 ])是正确的！

从《编程之美》给出的解法中得到启发，我们也只需要使用两个变量来记录m[ i+2 ]和m[ i+1 ]的值就行了，而且同样只需要O(N)的复杂度就可以解这道题，代码如下：

int maxsum(int* a, int n)
{
    int m2 = 0;
    int m1 = a[ n-1 ];
    for(int i = n - 2; i >= 0; i--)
    {
        if(m2 < 0) m2 = 0;  //处理最后一位为负数或全为负数的情况
        int tmp = m1;
        m1 = max(a[ i ] + m2, m1);
        m2 = tmp;
    }
    return m1;
}

hrlqq

我看过这书

ubuntuer

1. 
   
2. int MaxSub(const int A[], int N)
   
3. {
   
4.   int ThisSum;
   
5.   int MaxSum;
   
6.   int i;
   
7. 
   
8. for(i=0;i<N;i++)
   
9.   {
   
10.     ThisSum += A[i];
    
11. 
    
12.    if(ThisSum > MaxSum)
    
13.     MaxSum = ThisSum
    
14.   else if(ThisSum < 0)
    
15.    ThisSum = 0;
    
16.   }
    
17. return MaxSum
    
18. }
    

复制代码

aaaaa5aa

这个算法比较好

Maxshine

EMC曾经的笔试题。。。

weiqiboy

ubuntu的算法完全错误

weiqiboy

发表个跟楼主差不多的代码，算法思想相同，从低位扫描。

int maxsum(int array[], int n) { &nbsp;&nbsp;int i; &nbsp;&nbsp;int ret; &nbsp;&nbsp;int m0,m1; &nbsp;&nbsp;int temp; &nbsp;&nbsp;if(n < 2) &nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;if(n == 0) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return 0; &nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return max(0, array[0]); &nbsp;&nbsp;} &nbsp;&nbsp;ret = 0; &nbsp;&nbsp;m0 = 0; &nbsp;&nbsp;m1 = max(0, a[0]); &nbsp;&nbsp; &nbsp;&nbsp;for(i = 1; i < n; ++i) &nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;temp = max((m0 + array[i]), m1); &nbsp;&nbsp;&nbsp;&nbsp;m0 = m1; &nbsp;&nbsp;&nbsp;&nbsp;m1 = temp; &nbsp;&nbsp;} &nbsp;&nbsp;return ret; }

aaaaa5aa

能讲一下你的思路么

action08

书中循序渐进地通过分析给出了一个时间复杂度为O(N)空间复杂度为O(1)的最优解。