【算导】分治法求解最大子数组

任意子数组必然是以下三种情况之一：

1.完全在a[low…mid]中。

2.完全在a[mid+1…high]中。

3.跨越了数组中点。

若结果为1或2，则可通过递归求解，若结果为3，则可通过一个线性时间复杂度的函数求解：

FIND-CROSS(a,low,mid,high)
    leftsum=0;
    sum=0;
    for(int i=mid;i>=low;i--)
    {
        sum+=a[i];
        leftsum=max(leftsum,sum);
    }
    rightsum=0;
    sum=0;
    for(int i=mid;i<high;i++)
    {
        sum+=a[i];
        rightsum=max(rightsum,sum);
    }
return leftsum+rightsum

最后写一个总函数：

FIND(a,low,high)
    if(low==high)
        return a[low]
    else
    {
        mid=(low+high)/2
        b=FIND(a,low,mid)
        c=FIND(a,mid+1,high)
        d=FIND-CROSS(a,low,mid,high)
        return max(b,c,d);
    }

时间复杂度O(nlogn)

一个更优化的方法，时间复杂度O(n)
从头遍历，每遍历一个数，加到sum中，与当前最大值res比较更新res，当sum小于0时，sum、
等于0，相当于把之前的所有结果清零，从下一个数重新比较并继续更新res

int maxSubArray(vector<int> nums) {
    int ge = nums.size();
    if (ge == 0)
        return 0;
    int sum = 0;
    int res = nums[0];
    for (int i = 0; i < ge; i++)
    {
        sum += nums[i];
        res = max(sum, res);
        if (sum < 0)
            sum = 0;        
    }
    return res;
}