任意子數(shù)組必然是以下三種情況之一：

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

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

3.跨越了數(shù)組中點(diǎn)。

若結(jié)果為1或2，則可通過遞歸求解，若結(jié)果為3，則可通過一個(gè)線性時(shí)間復(fù)雜度的函數(shù)求解：

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

最后寫一個(gè)總函數(shù)：

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);
    }

時(shí)間復(fù)雜度O(nlogn)

一個(gè)更優(yōu)化的方法，時(shí)間復(fù)雜度O(n)
從頭遍歷，每遍歷一個(gè)數(shù)，加到sum中，與當(dāng)前最大值res比較更新res，當(dāng)sum小于0時(shí)，sum、
等于0，相當(dāng)于把之前的所有結(jié)果清零，從下一個(gè)數(shù)重新比較并繼續(xù)更新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;
}