最大子数组

股价每天都在变化，我们希望在一段时间中的最低点买入，在最高点卖出。给定一段时间的股价变化，如何确定最优的买入卖出时间？
如果把每天的股价抽象成一个数组，那么这个问题就是最大子数组问题：
给定一段时间的股价变化数组A，寻找A的和最大的非空连续子数组。
这个问题可以用分治法求解。把数组一分为二，最大的连续非空子数组要么完全在左边，要么完全在右边，要么横跨左右。取左边数组的最大子数组、右边数组的最大子数组、横跨左右的最大子数组中的最大者就得到了原来问题的解。
粗略地看，每次一分为二，递归求解的复杂度为

(是求解横跨左右的最大子数组的开销)

代码如下

#include<iostream>
#define inf 9999
using namespace std;

typedef struct res{
    int start,end;
    int msum;
}res;

res find_max_cross_subarr(int A[],int low,int mid,int high){
    int left_sum=-inf,right_sum=-inf;
    int sum=0;
    int max_left=mid,max_right=mid;
    for(int i=mid;i>=low;i--){
        sum+=A[i];
        if(sum>left_sum){
            left_sum=sum;
            max_left=i;
        }
    }
    sum=0;
    for(int j=mid+1;j<=high;j++){
        sum+=A[j];
        if(sum>right_sum){
            right_sum=sum;
            max_right=j;
        }
    }
    res myres={max_left,max_right,left_sum+right_sum};
    return myres;
}

struct res find_max_subarr(int A[],int low,int high){
    if(low==high){
        return res{low,high,A[low]};
    }
    int mid=(low+high)/2;
    res res1=find_max_subarr(A, low, mid);
    res res2=find_max_subarr(A, mid+1, high);
    res res3=find_max_cross_subarr(A, low, mid, high);
    if(res1.msum>res2.msum){
        if(res1.msum>res3.msum)
            return res1;
        else return res3;
    }else if(res2.msum>res3.msum)
        return res2;
    else return res3;
}

int main(){
    int arr[]={1,-1,2,4,5};
    res myres=find_max_subarr(arr, 0, 4);
    cout<<myres.start<<" "<<myres.end<<" "<<myres.msum<<endl;
    return 0;
}

输出

2 4 11

其实，这个问题还有一种更快的递推做法。从左向右扫描数组，A[1..j]的最大子数组要么是A[1..j-1]的最大子数组，要么是以A[j]结尾的子数组。
同时，我们从左往右记录和非负的子数组的开始下标low=m+1。如果A[l...m]之和为负，且m是使从l开始的子数组和为负的最小下标，那么任意的l<i<m，A[i...m]一定是负的(A[l...m]之和为负，A[l...i-1]之和为正)。因此在考虑以A[j]结尾的数组时无需考虑m及m之前的元素，加上这些元素只会使和变小，从m+1开始考虑即可。
这样，我们只需从左向右扫一遍数组，扫每个元素时更新下标low和最大子数组和相关信息。循环执行n次，每次执行常数时间的操作，算法复杂度。
代码如下

#include<iostream>
#define inf 9999
using namespace std;

typedef struct res{
    int start,end;
    int msum;
}res;

struct res find_max_subarr(int A[],int l){
    int Mr=0,low=0;
    int start=0,end=l,M=0-inf;
    for(int i=0;i<l;i++){
        Mr+=A[i];
        if(Mr>M){
            M=Mr;
            start=low;
            end=i;
        }
        if(Mr<0){
            Mr=0;
            low=i+1;
        }
    }
    return res{start,end,M};
}

int main(){
    int arr[]={-1,2,3,-4,1};
    res myres=find_max_subarr(arr, sizeof(arr)/sizeof(int));
    cout<<myres.start<<" "<<myres.end<<" "<<myres.msum<<endl;
    return 0;
}

输出

1 2 5