最大子序列和（分治求法）

这已经是一道家喻户晓的题了，给出一个数组，里面是一串数字，求出子序列中和最大的，输出这个和。

思路：这道题有很多经典解法，其中最典型应该是动态规划，而我们今天要讨论的是用二分法怎么求解这道题。

#include<iostream>

using namespace std;
int aleng;

int f(int a[],int begin,int end){
    if(end-begin==1){
        if(a[begin>0])return a[begin];
        return 0;
    }
    //求出左边一段的最大子序列和，
    //求出右边一段的最大子序列和，
    //求出由中间向两边扩展的最大子序列的和。
    //最后再比较这三者中最大的那个，就是我们要求出的答案了。
    int k=(begin+end)/2;
    int t1=f(a,begin,k);
    int t2=f(a,k,end);
    int t3a=0;
    int sum=0;

//好好领略下面这一段代码的编程思想。
    for(int i=k-1;i>=begin;i--){
        sum+=a[i];
        if(sum>t3a)t3a=sum; 
    }

    int t3b=0;
    sum=0;
    for(int i=k;i<end;i++){
        sum+=a[i];
        if(sum>t3b)t3b=sum;
    }
    int t3=t3a+t3b;


    int max=0;
    if(t1>max)max=t1;
    if(t2>max)max=t2;
    if(t3>max)max=t3;

    return max;
}

int work(int a[]){
    return f(a,0,aleng);
}
int main(){
    int a[]={2,4,-7,5,2,-1,2,-4,3};
    aleng=sizeof(a)/sizeof(int);
    cout<<work(a); 
    return 0;
}