https://leetcode-cn.com/problems/contiguous-sequence-lcci/
给定一个整数数组，找出总和最大的连续数列，并返回总和。
示例：
输入： [-2,1,-3,4,-1,2,1,-5,4] 输出： 6 解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶：
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
问题思路：
1.原数组分解为左右数组两部分。
2.求解左右数据的最大和，存在第三种情况，最大和存在于两个分段之间。
3.合并子问题的解。
代码设计思路：
1.涉及最大值比较需要返回最大值，因此return数据类型为int，同时也为该子问题的ans。
2.通过设计递归，必须使递归区间不断变小，因此使得mid = (l+r)/2。
3.面向最小递归区间设计递归出口，最小递归为(l, r)递归出口为 return nums[l](nums[r])。
伪代码：
// 递归出口
if l == r:
return this;
mid = (l+r)/2;
l_max = re(l, mid); // 左段递归
r_max = re(mid+1, r); // 右段递归
lr_max = (sum_l, sum_r); // 直接计算cross的最大值
return max(l_max, r_max. lr_max);
1 class Solution { 2 public: 3 4 int dfs(vector<int>& nums, int l, int r){ 5 if(l==r) 6 return nums[l]; 7 int mid_ = (l+r)/2; 8 // left 9 int l_max = dfs(nums, l, mid_); 10 // right 11 int r_max = dfs(nums, mid_+1, r); 12 13 // cross 14 int l_sum = INT_MIN; 15 int sum = 0; 16 // 左边分为[0, mid] 右边[mid+1, r] 17 for(int i=mid_; i>=l; i--){ 18 sum += nums[i]; 19 l_sum = max(sum, l_sum); 20 } 21 22 int r_sum = INT_MIN; 23 sum = 0; 24 for(int i=mid_+1; i<=r; i++){ 25 sum += nums[i]; 26 r_sum = max(sum, r_sum); 27 } 28 29 int max_ = max(l_sum+r_sum, max(l_max, r_max)); 30 31 32 return max_; 33 } 34 int maxSubArray(vector<int>& nums) { 35 if(nums.size()==0) 36 return 0; 37 return dfs(nums, 0, nums.size()-1); 38 } 39 };