参考链接https://www.cnblogs.com/wkfvawl/p/11535615.html

如何用分治法求解最大子段和问题

在数组的 center = (right-left)/2+left 位置处分开。形成两个子数组。

那么，最大子段和 可能出现在三个位置：

a.可能出现在 左 子数组

b. 可能出现在 右子数组

c.可能出现在 过center的 中间某部分 元素 组成的子数组。

下面考虑 三种情况的计算方法：

第一种情况： 计算 left 到 center 的最大和，记作 leftSum

第二种情况： 计算从 center+1 到 right的最大和，记作 rightSum

第三种情况： 跨边界的和。 以center为中心分别向两边计算和。

a.从 center出发，每次向左边扩张一步，并且记录当前的值S1，如果当前的和比上次的和大，就更新S1，一直向左扩张到位置 Left。

b.从 center+1出发，每次扩张一步，计算当前的和 为S2，如果当前的值比上次的和 大，那么，就更新S2的值，一直向右扩张到位置Right。

c.计算过center的连续值的和，S1+S2的值 Sum。 这个就是跨边界的和。

上面三种情况考虑计算完成后，最后一步就是，比较三个值中的最大值，取最大值就可以了。

时间复杂度为(nlogn)

#include <iostream>

using namespace std;

const int N = 110;

int n;
int a[N];

int maxSubSum(int a[], int left, int right)
{

    int sum = 0;
    if(left == right)
    {
        sum = a[left] > 0 ? a[left] : 0;
    }
    else{

        int center = (left + right) / 2;
        int leftSum = maxSubSum(a, left, center);
        int rightSum = maxSubSum(a, center + 1, right);

        int s1 = 0;
        int lefts = 0;
        for(int i = center; i >= left; i--){

            lefts += a[i];
            if(lefts > s1) s1 = lefts;
        }

        int s2 = 0;
        int rights = 0;
        for(int i = center + 1; i < right; i++){

            rights += a[i];
            if(rights > s2) s2 = rights;
        }
        sum = s1 + s2;
        if(sum < leftSum) sum = leftSum;    
        if(sum < rightSum) sum = rightSum;
    }
    return sum;
}

int maxSum(int a[], int n)
{
    return maxSubSum(a, 0, n - 1);
}


int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)  cin >> a[i];
    cout << "最大连续子段和为" << maxSum(a, n) << endl;

    return 0;
}