算法一：动态规划

动态规划问题。定义f[i]为以nums[i]为结尾子序列的最大值，那么f[i]怎么求呢？将f[i]分为两类，①：只包含nums[i]一个数 ②：还有其他的数。第一种情况很好求就是nums[i]，第二种情况为f[i - 1] + nums[i]，所以f[i] = max(0, f[i - 1]) + nums[i]，然后又可以用滚动数组的思想省去空间改成s = max(0, s) + nums[i]。

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        for (int i = 1, s = nums[0]; i < nums.length; i++) {
            s = nums[i] + Math.max(0, s);
            ans = Math.max(ans, s);
        }
        return ans;
    }
}

算法二：分治

先找到中点mid，将区间一分为二[l, mid][mid + 1, r]，所有的子序列只有三种情况：

1. 在左区间内部，就是这样：
    [      ]  
[l,        mid][mid + 1,         r] 
2. 在右区间内部，就是这样：
                  [       ]          
[l,        mid][mid + 1,         r]  
3. 两个区间都有，就是这样：
        [             ]               
[l,        mid][mid + 1,         r]   

然后对于这三种情况取max就可以了。

class Solution {
    public int maxSubArray(int[] nums) {
        return getMax(nums, 0, nums.length - 1);
    }
    public int getMax(int[] nums, int l, int r) {
        if (l >= r) return nums[l];
        int mid = l + r >> 1;
        int res = Math.max(getMax(nums, l, mid), getMax(nums, mid + 1, r));
        int leftMax = nums[mid];
        for (int i = mid - 1, s = nums[mid]; i >= l; i--) {
            s += nums[i];
            leftMax = Math.max(leftMax, s);
        }
        int rightMax = nums[mid + 1];
        for (int i = mid + 2, s = nums[mid + 1]; i <= r; i++) {
            s += nums[i];
            rightMax = Math.max(rightMax, s);
        }
        res = Math.max(res, leftMax + rightMax);
        return res;
    } 
}