首页 > 代码库 > 归纳法求解最大连续子序列

归纳法求解最大连续子序列

(原文链接:http://www.karottc.com/blog/2014/09/07/maximum-consecutive-subsequence/)

问题

求最大连续子序列的问题描述如下:

给定一个实数序列 x1, x2, ... , xn(不必是正数),寻找一个(连续的)子序列 xi, xi+1, ... , xj,使得其数值之和在所有连续子序列数值之和中是最大的。

这个问题就是最大子序列问题,所求的的这个序列就叫做——最大子序列。下面通过数学归纳法来分析和解决这个问题,解决这个问题的最好目标是: 一个算法,能够只扫描此序列一次就得到最大子序列

归纳分析

根据上面的问题可以直接得到一般的归纳假设:

归纳假设: 已知如何找到规模小于 n 的序列的最大子序列。

下面假定一些变量:

  • 给定序列 S(n)=(x1, x2, ... , xn).
  • 序列 S(n) 的子序列为 S(n) .
  • 序列 S(n) 的最大子序列为 SM(n)=(xi, xi+1, ... , xj).
  • 序列 S(n) 的最大后缀子序列为 SE(n)=(xk, xk+1, ... , xn). 

现在开始用数学归纳法来证明:

  1. 当 n = 1 时, S(1)=x1,如果 x1<0,则 *SM(1)=NULL;否则 *SM(1)=x1 .
  2. 当 n = n-1 时,S(n-1)=(x1, x2, ... , xn-1),假设 SM(n-1)=(xi, xi+1, ... , xj).
  3. 当 n = n 时,S(n)=(x1, x2, ... , xn)=( S(n-1), xn),然后由 SM(n-1) 推导出 SM(n),共有下面3种情况:

    1. SM(n-1)=(xi, xi+1, ... , xj) = NULL,如果 xn<0,则 *SM(n)=NULL;否则 *SM(n)=xn .
    2. SM(n-1)=(xi, xi+1, ... , xj) && j = n-1,此时 SM(n-1) = SE(n-1),如果 xn > 0,SM(n)= SM(n-1) + xn = (xi, xi+1, ... , xj) + xn,否则 SM(n)= SM(n-1)=(xi, xi+1, ... , xj) .
    3. SM(n-1)=(xi, xi+1, ... , xj) && j < n-1,此时 SM(n-1) > SE(n-1),则可得到 SM(n)SM(n-1) 或者 SM(n)SE(n-1) + xn .
  4. 即上述可得证:能够求出 S(n)=(x1, x2, ... , xn) 的最大连续子序列,不过上述的证明过程中用了增强归纳假设,这个也是这个证明的关键:

    更强的归纳假设: 已知如何找到规模小于 n 的序列的最大子序列,以及作为后缀的最大子序列。

我们知道了 SM(n) 和 SE(n) 这两个序列,算法也就明确了。我们把 xn 加入到最大后缀子序列中,如果它的和大于原来的最大子序列,则得到一个新的最大子序列(同样也是一个后缀),否则,保留以前的最大子序列。但求解过程还没有结束,我们还需要寻找新的最大后缀子序列,因为不能只是简单的把 xn 加到以前的最大后缀中,有可能以 xn 结束的最大后缀的和是负数,在这种情况下,我们就需要把NULL(空集)作为最大后缀(以及把随后的 xn+1 也考虑进去)。

具体算法实现

根据上面的分析过程,下面贴上具体的C++代码:

int Maximum_Consecutive_Subsequence(int *x, int n)                                 
{                                                                                  
    int global_Max = 0;   // 最大子序列的和                                        
    int suffix_Max = 0;   // 最大后缀子序列的和,每次迭代都会更新                  
    int i = 0;                                                                     
    for (i = 0; i < n; i++)                                                        
    {                                                                              
        if (x[i] + suffix_Max > global_Max)                                                                  
        {                                                                          
            suffix_Max = suffix_Max + x[i];                                        
            global_Max = suffix_Max;                                               
        }                                                                          
        else if (x[i] + suffix_Max > 0)                                            
        {                                                                          
            suffix_Max = suffix_Max + x[i];                                        
        }                                                                          
        else                                                                       
        {                                                                          
            suffix_Max = 0;                                                        
        }                                                                          
    }                                                                              
    return global_Max;                                                             
}

更详细的代码可以戳这里. 

2014.09.07


归纳法求解最大连续子序列