专栏首页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)=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]【算法拾遗】三种方法求连续子数组的最大和

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 面向对象设计原则(1)——学习使用设计模式

    设计模式(Design Pattern)是一套被反复使用、多数人知晓、分类编目、代码设计经验的总结。使用设计模式是为了提高代码的可复用性、可扩充性可维护性,让代...

    Dabelv
  • 腾讯2016春季校园实习招聘技术岗复试(二面)问题汇总(CC++后台)

    2016.4.12日下午在广州东圃参加了腾讯安全技术面的二面。一面是两天前下午4点多结束,晚上大概十点多接到复试(二面技术面)的通知。晚上回来就开始整体一面的问...

    Dabelv
  • Linux 命令(110)—— help 命令(builtin)

    help 命令只能显示 Bash 内部命令的帮助信息,对于外部命令的帮助信息需要使用 man 或 info 命令查看。

    Dabelv
  • Lync在线用户查询

        Lync部署完毕后,哪些用户在登录,有没有方法查询到?使用不同的终端登录能不能统计并查询到?

    杨强生
  • 2020年,这10 个 非常热门的Java 微服务框架,你知道吗?

    Java 构建 Spring 应用程序已经有很长一段时间了,Spring Boot 是 Spring 的一个特定版本,它通过对配置细节的处理,使微服务构建更加简...

    秃顶的Java程序员
  • 最热门的 10 个 Java 微服务框架

    Java 构建 Spring 应用程序已经有很长一段时间了,Spring Boot 是 Spring 的一个特定版本,它通过对配置细节的处理,使微服务构建更加简...

    淡定的蜗牛
  • Python+Selenium笔记(十):元素等待机制

    (一) 前言 突然的资源受限或网络延迟,可能导致找不到目标元素,这时测试报告会显示测试失败。这时需要一种延时机制,来使脚本的运行速度与程序的响应速度相匹配,W...

    free赖权华
  • Hibernate之延迟加载

    爱撒谎的男孩
  • 其他需求 | 常见问题

    其他需求 1.我们的工作环境是内网,腾讯位置服务地图是否能够提供离线支持? 腾讯位置服务API是一个在线服务的互联网地图平台,我们的定位、搜索、地图、导航等所...

    腾讯位置服务
  • centos6.7自带python升级为

      昨天因为工作的需要,将centos6.7自带的python升级为2.7。其中,遇到了一些小波折,来记录一下,大家遇到相似问题可以做个参考。

    用户2398817

扫码关注云+社区

领取腾讯云代金券