算法竞赛入门经典（第二版）-分治法_8.1.3

分治法的思路不难理解：
1，划分问题：把问题的实例划分成子问题
2，递归求解：递归解决子问题
3，合并问题：合并子问题的解得到原问题的解

但是本人在看 求最大连续和 这道例题时对一个地方疑惑了很久。

求序列最大连续和，可将序列从中间一分为2，递归求左序列的最大连续和，再递归求右序列的最大连续和。结果就在这单独左右的最大和值，和既包括左又包括右序列的序列最大和值之中产生。

求左右最大和值没问题，那怎样求中间序列的最大和值呢？

答案是从中间分开位置开始，往左遍历求得左边连续序列的最大和值，再求从中间位置开始往右的最大和值。

左连续的最大和值 + 右连续最大和值 + 中间位置值 = 包括中间位置连续序列的最大和值。

这里的求左连续的最大和值和我们刚开始求左最大和值操作不同，这里必须要连着中间值。

比如 1 9 -2 3 4 5 刚开始我们求1 9 -2 的连续最大和的值显然是1+9 = 10，但是求包括中间位置的最大连续序列和值时，我们必须计算 -2 在内，即 1 + 9 + -2 = 8。

下面是测试代码，默认y为5，可以自行更改。

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

int maxsum(int *A, int x, int y){

    int v, L, R, maxs;
    if(y-x == 1)
        return A[x];
    int m = x + (y-x)/2;
    cout<<x<<" "<<y<<" "<<m<<endl;
    maxs = max(maxsum(A, x, m), maxsum(A, m, y));
    v=0; L = A[m-1];
    for(int i=(m-1);i>=x;i--)
        L = max(L, v += A[i]);
    v=0; R = A[m];
    for(int i=m;i<y; i++)
        R = max(R, v += A[i]);
    cout<<"L: "<<L<<endl<<"R: "<<R<<endl<<endl;
    return max(maxs, L+R);

}

int main(){
    int a[100] = {0};
    int n = 5;
    for(int i=0;i<5;i++){
        cin>>a[i];
    }
    int res = maxsum(a,0,5);
    cout << res;
    getchar();
    getchar();
    return 0;
}