给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
思路:
基础分而治之：left_Part、right_Part 和cross_Value三种情况
class Solution {
public:
int maxSubArray(vector<int>& nums)
{
int len = nums.size();
if(len == 0)
return 0;
else
return maxSub(0, len-1, nums);
}
```
int maxSub(int low , int high,vector<int>& nums)
{
if(low == high)
return nums[low];
int mid = low + (high - low) / 2;
int left = maxSub(low, mid,nums);
int right = maxSub(mid+1, high,nums);
int cross = nums[mid];
int sum = nums[mid];
for (int i = mid - 1; i>=low; i--)
{
sum += nums[i];
cross = max(cross,sum);
}
sum = cross;
for(int i = mid+1; i<=high; i ++)
{
sum += nums[i];
cross = max(cross, sum);
}
return max(left, max(right, cross));
}
};
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
def maxSub(low, high):
mid = low + (high - low) // 2
if (low == high):
return nums[low]
else:
left = maxSub(low, mid)
right = maxSub(mid + 1, high)
cross_Left = nums[mid]
sum = nums[mid]
i = mid - 1
while(i >= low):
sum += nums[i]
cross_Left = cross_Left if cross_Left > sum else sum
i -= 1
cross_Right = nums[mid + 1]
sum = nums[mid + 1]
i = mid + 2
while(i <= high):
sum += nums[i]
cross_Right = cross_Right if cross_Right > sum else sum
i += 1
cross_Right = cross_Right if cross_Right > sum else sum
cross = cross_Left + cross_Right
return max(left, right, cross)
return maxSub(0,len(nums) - 1)
```