由53.最大子序和分治法解决方案引出（动态规划方法easy不谈）

    1. class Solution {
    2. public:
    3.     struct State{
    4.         int lSum;//以l为左端点的最大子段和
    5.         int rSum;//以r为右端点的最大字段和
    6.         int mSum;//区间内最大子段和
    7.         int tSum;//区间和
    8.     };
    9.     State pushUp(State l, State r){
    10.         int lSum = max(l.lSum, l.tSum + r.lSum);
    11.         int rSum = max(r.rSum, l.rSum + r.tSum);
    12.         int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
    13.         int tSum = l.tSum + r.tSum;
    14.         return (State) {lSum, rSum, mSum, tSum};
    15.     }
    16.     State search(vector<int> &nums, int l, int r){
    17.         if (l == r) {
    18.             return (State) {nums[l], nums[l], nums[l], nums[l]};
    19.         }
    20.         int m = l + (r - l) / 2;//如果是 l + (r - l) >> 1会报栈溢出，另外三种写法都没有问题
    21.         State lSub = search(nums, l, m);
    22.         State rSub = search(nums, m + 1, r);
    23.         return pushUp(lSub, rSub);
    24.     }
    25.     int maxSubArray(vector<int>& nums) {
    26.         if(nums.empty())return 0;
    27.         return search(nums, 0, nums.size() - 1).mSum;
    28.     }
    29. };