题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

解题方法

贪心
局部最优：子串和为正，对和为负的子串舍去。
全局最优：和最大的子串。
时间复杂度O(n)，空间复杂度O(1)
C++代码：
```
class Solution {
public:
  int maxSubArray(vector<int>& nums) {
      int maxsum = INT_MIN;
      int sum = 0;
      for(int i=0; i<nums.size(); i++) {
          sum+=nums[i];
          maxsum = maxsum > sum ? maxsum : sum;
          if(sum<0) sum = 0;
      }

      return maxsum;
  }
};
```
动态规划
使用sum记录以当前数字为结尾的子数组的最大和，则有递推关系如下：

使用maxsum记录最大的sum值即可。
时间复杂度额O(n)，空间复杂度O(1)
C++代码：
```
class Solution {
public:
  int maxSubArray(vector<int>& nums) {
      int maxsum = INT_MIN;
      int sum = 0;
      for(int i=0; i<nums.size(); i++) {
          sum = max(sum+nums[i], nums[i]);
          maxsum = maxsum > sum ? maxsum : sum;
      }

      return maxsum;
  }
};
```
分治法
对于一个区间[l, r]，定义getmaxsub(nums, l, r)获取数组在区间[l, r]上的最大子数组和。通过m = (l+r)/2将数组分为两部分，递归求解，当l=r时进行回升，合并结果。
对于区间[l, r]，定义如下状态变量以方便递归求解过程中的区间结果合并：
- lsum：以l为子区间左端点的最大子数组和。
- rsum：以r为子区间右端点的最大子数组和。
- msum：区间[l, r]的最大子数组和。
- isum：区间和

上述状态变量在合并子区间left = [l, m]和right = [m+1, r]时其更新方法如下：

当子区间长度为1时，lsum = rsum = msum = isum = nums[l]。
对于isum，其值为左子区间的isum与右子区间isum的和，即isum = left.isum + right.isum。
对于lsum，其值为左子区间的lsum和左子区间isum与右子区间lsum和之间的最大值，即lsum = max(left.lsum, left.isum + right.lsum)。
对于rsum，其值为右子区间的rsum和右子区间isum与左子区间rsum和之间的最大值，即rsum = max(right.rsum, right.isum + left.rsum)。
对于msum，其值为左子区间msum、右子区间msum、左子区间rsum与右子区间lsum和三者之间的最大值，即msum = max(max(l.msum, r.msum), r.lsum+l.rsum)

分治法的意义在于，在大规模的场景下，通过将所有子数组的状态保存成树的格式，可以在O(logn)的时间复杂度内求解任意区间内的最大子数组和，并且当数组发生修改后也仅需要简单的维护状态树即可。
时间复杂度O(n)，空间复杂度O(logn)
C++代码：

class Solution {
public:
    struct status {
        int lsum, rsum, msum, isum;
    };

    status merge(status l, status r) {
        int isum = l.isum + r.isum;
        int lsum = max(l.lsum, r.lsum + l.isum);
        int rsum = max(r.rsum, l.rsum + r.isum);
        int msum = max(max(l.msum, r.msum), r.lsum+l.rsum);
        return  (status){lsum, rsum, msum, isum};
    }

    status getmaxsub(vector<int>& nums, int l, int r) {
        if(l==r)    return (status){nums[l], nums[l], nums[l], nums[l]};
        int m = (l+r)/2;
        status left = getmaxsub(nums, l, m);
        status right = getmaxsub(nums, m+1, r);
        return merge(left, right);
    }

    int maxSubArray(vector<int>& nums) {
        return getmaxsub(nums, 0, nums.size()-1).msum;
    }
};

LeetCode

53. 最大子数组和

题目

解题方法

贪心

动态规划

分治法