最大子数组问题

恋喵大鲤鱼

发布于 2018-08-03 15:55:26

8320

发布于 2018-08-03 15:55:26

文章被收录于专栏：C/C++基础

1.问题背景

炒股的人都知道，股票的价格是不稳定的。若想从炒股中赚钱，必须“低买高卖”，就是低价买进，高价卖出，赚取中间差价。那么给定一段时间，每一天都对应着不同的股价，如何确定哪天买进，哪天卖出可以获得最大收益呢？

其实我们可以很容易设计出一个暴力的方法来求解本问题，即简单地尝试每对可能的买进和卖出的日期组合，只要卖出日期在买入日期之后即可。n天中共有C2n=12n(n−1)C_n^2=\frac{1}{2}n(n-1)，因此其复杂度为O(n2)O(n^2)。

2.问题变换

上面描述的炒股选取适当买入和卖出的日期来达到收益的最大化，从一个稍微不同的角度来看待输入数据。我们的目的是寻找一段日期，使得从第一天到最后一天的股票价格净变值最大。因此，我们不再从每日价格的角度去看待输入数据，而是考察每日价格变化，第i天的价格变化定义为第 i 天和第 i-1 天的价格差。假设会有如下价格差：

我们可以将上面的一行数据看成一个数组A，那么问题就转化为寻找A的和最大的非空连续字数组。我们称这样的连续子数组为最大子数组（maximum subarray）。

在一个数组中，只有当数组中包含负数时，最大字数组问题才有意义，而且很有可能存在多个相同和的最大子数组。

3.使用分治策略求解最大子数组

使用分治法来求解最大子数组问题是为了提高求解速率。注意：请仔细研读下面的解析和求解的步骤和思想，以及伪代码，这样就可以明白整个过程和后面给出的示例代码。

假设我们要寻找子数组A[low,…,high]的最大子数组。使用分治意味着我们要将子数组划分为两个规模尽量相等的子数组。也就是说，找到子数组的中央位置，比如mid，然后考虑求解两个子数组A[low,…,high]和A[mid+1,…,high]。

如下图所示，A[low,…,high]任何连续子数组A[i,…,j]所处的位置必然是以下三种情况之一：（1）完全位于子数组A[low,…,mid]中，因此low≤i≤j≤midlow\leq i\leq j\leq mid。（2）完全位于子数组A[mid+1,…,high]中，因此mid<i≤j≤highmid< i\leq j\leq high。（3）跨越了中点，因此A[low,…,mid]中，因此low≤i≤mid<j≤midlow\leq i\leq mid<j\leq mid。

对于A[low,mid]和A[mid+1,high]，可以递归求解，因为这两个子问题仍是最大子数组问题，只是规模更小。因此，剩下的工作就是寻找跨越中点的最大字数组，然后在三种情况中选取和最大者。

求跨越中点的最大字数组并非原问题规模更小的实例，因为它加入了限制——求出的字数组必须跨越中点。因此，我们只要找出形如A[i,mid]和A[mid+1,j]的最大子数组，然后将其合并即可。

过程FIND-MAX-CROSSING-SUBARRAY接收数组A和下标low、mid和high为输入，返回一个下标元组标明跨越中点的最大子数组的边界，并返回最大子数组中值的和。其伪代码如下：

FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high)
    left-sum=-∞
    sum=0
    for i=mid downto low
        sum=sum+A[i]
        if sum>left-sum
            left-sum=sum
            max-left=i
    right-sum=-∞
    sum=0
    for j=mid+1 to high
        sum=sum+A[j]
        if sum>right-sum
            right-sum=sum
            max-right=j
    return (max-left,max-right,left-sum+right-sum)

上述伪代码容易理解且不难实现，就是查找跨越中点的最大子数组。伪代码中两次for循环的每次迭代华为O(1)的时间，我们只需要统计一共执行了多少次迭代。第一个for迭代的次数是mid-low+1，第二次for迭代的次数是high-mid次，因此总循环迭代次数为n，时间复杂度为O(n)。

有了一个线性时间的FIND-MAX-CROSSING-SUBARRAY在手，我们可以设计求解最大子数组问题的分治算法的伪代码了。

FIND-MAXIMUM-SUBARRAY(A,low,high)
    if high==low
        return (low,high,A[low]) //base case:only one element
    else mid=⌊(low+high)/2⌋
        (left-low,left-high,left-sum)=FIND-MAXIMUM-SUBARRAY(A,low,mid)
        (right-low,right-high,right-sum)=FIND-MAXIMUM-SUBARRAY(A,mid+1,high)
        (cross-low,cross-high,cross-sum)=FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high)
        if left-sum>right-sum and left-sum>cross-sum
            return (left-low,left-high,left-sum)
        else if right-sum>left-sum and right-sum>cross-sum
            return (right-low,right-high,right-sum)
        else return (cross-low,cross-high,cross-sum)

4.分治策略求解复杂度分析

分治策略求解最大子数组使用了递归求解的方法，因此我们需要建立一个递归式来描述上面算法的时间复杂度。

在这里，对问题进行简化，假设原问题是规模的2的幂，这样所有子问题的规模均为整数。我们用T(n)表示FIND-MAXIMUM-SUBARRAY求解n个元素的最大子数组的运行时间。当n=1，很明显：

T(1)=O(1)

T(1)=O(1) 当n>1时为递归情况，需要将原数组划分为2个规模为n/2个元素的子数组进行求解，因此每个子数组求解时间为T(n/2)。由上面可知，求解跨中点的最大子数组需要O(n)的时间复杂度。因此，对于递归的情况，我们有：

T(n)=2T(n/2)+O(n)

组合上面两个公式，得到求解最大子数组的运行时间T(n)的递归式：

T(n)={O(1),n=12T(n/2)+O(n),n>1

T(n)=\left\{ \begin{aligned} O(1) \hspace{2.4cm}, n=1\\ 2T(n/2)+O(n),n>1\end{aligned}\right.

此递归式与归并排序的递归式一样，求解递归式的时间复杂度可以采用《算法导论中》中文第三版的4.5中提出的方法，可快速求解上面递归式的时间复杂度T(n)=O(nlgn)。但是我建议应该以数学的方式去精确求解T(n)的表达式，求解的方法可见：解递归方程。

5.示例代码

#include <iostream>

using namespace std;

struct MaximumSubarray{
    int low;
    int high;
    int sum;
};

/******************************
func:求跨越中点的最大子数组
para:A:数组;low:左下标;mid:中下标;high:右下标
******************************/
MaximumSubarray findMaxCrossingSubarr(int A[],int low,int mid,int high){
    int left_sum=0x80000000;//最小负数
    int right_sum=0x80000000;//最小负数
    int max_left=0;
    int max_right=0;
    int sum=0;
    MaximumSubarray maxSubarr={0};

    for(int i=mid;i>=low;--i){
        sum+=A[i];
        if(sum>left_sum){
            left_sum=sum;
            max_left=i;
        }
    }
    sum=0;
    for(int i=mid+1;i<=high;++i){
        sum+=A[i];
        if(sum>right_sum){
            right_sum=sum;
            max_right=i;
        }
    }
    maxSubarr.low=max_left;
    maxSubarr.high=max_right;
    maxSubarr.sum=left_sum+right_sum;
    return maxSubarr;
}

/***********************************
func:求给定数组的最大子数组
para:A:数组;low:左下标;high:右下标
***********************************/
MaximumSubarray findMaxSubarr(int A[],int low,int high){
    MaximumSubarray maxSubarrLeft={0};
    MaximumSubarray maxSubarrRight={0};
    MaximumSubarray maxSubarrCross={0};
    if(high==low){          //特殊情况：只有一个元素
        maxSubarrLeft.low=low;
        maxSubarrLeft.high=high;
        maxSubarrLeft.sum=A[low];
        return maxSubarrLeft;  
    }
    int mid=(low+high)/2;
    maxSubarrLeft=findMaxSubarr(A,low,mid);
    maxSubarrRight=findMaxSubarr(A,mid+1,high);
    maxSubarrCross=findMaxCrossingSubarr(A,low,mid,high);
    if(maxSubarrLeft.sum>maxSubarrRight.sum&&maxSubarrLeft.sum>maxSubarrCross.sum)
        return maxSubarrLeft;
    else if(maxSubarrRight.sum>maxSubarrLeft.sum&& maxSubarrRight.sum>maxSubarrCross.sum)
        return maxSubarrRight;
    else return maxSubarrCross;
}

int main(int argc,char* argv[]){
    int A[16]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
    MaximumSubarray resMaxSubarr=findMaxSubarr(A,0,15);
    cout<<"maximum subarray is:"<<endl;
    cout<<"resMaxSubarr.low:"<<resMaxSubarr.low<<endl;
    cout<<"resMaxSubarr.high:"<<resMaxSubarr.high<<endl;
    cout<<"resMaxSubarr.sum:"<<resMaxSubarr.sum<<endl;
    return 0;
}

以代码中的数组为例，输出结果如下：

6.动态规划法求解

阅读上文，我们看到了利用分治法得到了一个渐进复杂度优于暴力的求解方法的算法。有时候，对某个问题，分治法能给出渐进最快的算法，而其他时候，我们不用分治法甚至做的更好。对于最大子数组问题，实际上还可以不用分治法，在线性时间内求解。

6.1算法思想

以下方法是一个非递归的，线性时间的算法。算法思想描述如下：

对数组由左至右处理，记录已经处理的最大子数组。若已知A[0,j]的最大子数组，A[0,j+1]的最大子数组要么是某个子数组A[i,j+1](0≤i≤j+1)(0\leq i\leq j+1)，要么是A[0,j]的最大子数组。在已知A[0,j]最大子数组的情况下，可以在线性时间内找出A[0,j+1]的最大子数组。

6.2动态规划法求解过程描述

以上算法思想时间是采用了动态规划的方法来设计求解算法。对于动态规划，其思想是由上一阶段的问题的解（可能被分解为多个子问题）递推求解出最终问题的。这里就要知道两个东西。一是问题的状态，而是状态转移方程。

这个问题的状态是怎么找出来的呢？可根据子问题来定义状态。设max(0,i)表示数组A[0,i]的最大子数组，那么问题的状态就是max(0,i)。

那么状态转移方程就是如何通过max(0,i)推导出max(0,i+1)。这里的max(0,i+1)就是数组A[0,i+1]的最大子数组。根据上面的描述得出，

max(0,i+1)=max{max(0,i),sum(j,i)+A[i+1]},0≤j≤i

max(0,i+1)=max \{max(0,i),sum(j,i)+A[i+1]\}, 0\leq j\leq i 其中，sum(j,i)+A[i+1]sum(j,i)+A[i+1]表示数组元素A[j]到元素A[i]的和再加上A[i+1]。

已知初始状态max(0,0)=A[0]，有了状态和状态转移方程，逐步递推到max(0,n-1)，这就是最终的解。

6.3伪代码

结合上面的动态规划过程的分析，可以给出如下伪码。首先我们要求出max{sum(j,i)+A[i+1]},0≤j≤imax \{sum(j,i)+A[i+1]\},0\leq j\leq i ，伪码如下：

FIND-MAX-ARRAY(A,low,high)
    if high==low
        return (low,high,A[low])
    max-left=low
    max-right=high
    sum=A[high]
    tmp-sum=A[high]
    for i=high-1 downto low
         tmp-sum+=A[i]
         if tmp-sum>sum
             sum=tmp-sum
             max-left=i
    return (max-left,max-right,sum)

根据上面的max{sum(j,i)+A[i+1]},0≤j≤imax \{sum(j,i)+A[i+1]\},0\leq j\leq i 和状态转移方程，我们就可以求出max(0,i+1)，即数组A[0,i+1]的最大子数组。

FIND-MAXIMUM-SUBARRAY(A,low,high)
    if high==low
        return (low,high,A[low])
    max-left=low
    max-right=low
    sum=A[low]
    for i=low+1 to high
        (new-left,new-right,new-sum)=FIND-MAX-ARRAY(A,low,i)
        if(new-sum>sum)
            (max-left,max-right,max-sum)=(new-left,new-right,new-sum)
    return (max-left,max-right,max-sum)

6.4示例代码

结合伪代码，很容易写出实现的代码。

//dynamic programming method
/**********************************************
func:获取以high为起始下标向左至low下标的最大子数组
para:A:数组;low:起始下标;high:结束下标
**********************************************/
MaximumSubarray FIND_MAX_ARRAY(int A[],int low,int high){
    MaximumSubarray maxSubarr={0};
    if (high==low){
        maxSubarr.low=low;
        maxSubarr.high=high;
        maxSubarr.sum=A[low];
        return maxSubarr;
    }
    maxSubarr.low=high;
    maxSubarr.high=high;
    maxSubarr.sum=A[high];
    int tmp_sum=A[high];
    for (int i=high-1;i>=low;--i){
         tmp_sum+=A[i];
         if(tmp_sum>maxSubarr.sum){
             maxSubarr.sum=tmp_sum;
             maxSubarr.low=i;
         }
    }
    return maxSubarr;
}

/***********************************************
func:求给定数组的最大子数组
para:A:数组;low:起始下标;high:结束下标
***********************************************/
MaximumSubarray FIND_MAXIMUM_SUBARRAY(int A[],int low,int high){
    MaximumSubarray maxSubarr={0};
    if (high==low){
        maxSubarr.low=low;
        maxSubarr.high=high;
        maxSubarr.sum=A[low];
        return maxSubarr;
    }

    maxSubarr.low=low;
    maxSubarr.high=low;
    maxSubarr.sum=A[low];
    MaximumSubarray tmpSubarr={0};
    for (int i=low+1; i<=high;++i)
        tmpSubarr=FIND_MAX_ARRAY(A,low,i);
        if(tmpSubarr.sum>maxSubarr.sum)
            maxSubarr=tmpSubarr;
    return maxSubarr;
}

int main(int argc,char* argv[]){
    int A[16]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
    MaximumSubarray resMaxSubarr=FIND_MAXIMUM_SUBARRAY(A,0,15);
    cout<<"dynamic programming maximum subarray is:"<<endl;
    cout<<"resMaxSubarr.low:"<<resMaxSubarr.low<<endl;
    cout<<"resMaxSubarr.high:"<<resMaxSubarr.high<<endl;
    cout<<"resMaxSubarr.sum:"<<resMaxSubarr.sum<<endl;
    return 0;
}

还是以代码中的数组为例，输出结果如下，与分治法求解结果相同：

7.扫描法

对于一个包含负数的数组，从数组左边开始，依次累加元素和，当小于0时，从下一个元素重新开始累加并与前面最大子数组的和比较，记录最大者。

int MaxSubSum3(int *arr,int len){  
    int i;  
    int MaxSum = 0;  
    int CurSum = 0;  
    for(i=0;i<len;i++){  
        CurSum += arr[i];  
        if(CurSum > MaxSum)  
            MaxSum = CurSum;  
        //如果累加和出现小于0的情况,
        //则最大和子序列肯定不可能包含前面的元素，  
        //这时将累加和置0，从下个元素重新开始累加  
        if(CurSum < 0)  
            CurSum = 0;  
    }  
    return MaxSum;  
}

显然，该算法的时间复杂度O（n），理解起来应该不难，但是要想出来可就不容易了。另外，该算法的一个附带的有点是：它只对数据进行一次扫描，一旦元素被读入并被处理，它就不再需要被记忆。因此，如果数组在磁盘或磁带上，他就可以被顺序读入，在主存中不必存储数组的任何部分。不仅如此，在任意时刻，该算法都能对它已经读入的数据给出最大子数组（另外两种算法不具有这种特性）。具有这种特性的算法叫做联机算法。

参考文献

[1]算法导论中文版.原书第三版[M].38-42 [2]http://www.360doc.com/content/13/0601/00/8076359_289597587.shtml [3]【算法拾遗】三种方法求连续子数组的最大和

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016年03月13日，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度