53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
这道题不能用滑动窗口来做，因为数组中含有复数，这样就无法决定窗口的大小。
和为S的连续正数序列 中便用到了滑动窗口
思路可看官方题解，讲的很清楚，这里不再赘述… 也可参考 labuladong
方法一：动态规划
class Solution { public int maxSubArray(int[] nums) { int tmp = 0; // tmp 表示以nums[i]为结尾时的最大子序和，我们的目的是求得所有的，然后找出最大的 int res = nums[0]; // res表示到目前nums[i]为止，之前以 nums[k],0≤k≤i 为结尾的所有最大子序和的最大值。 for(int each : nums){ tmp = Math.max(tmp + each, each); res = Math.max(res, tmp); } return res; } }时间复杂度：O(n)
空间复杂度：O(1)
方法二：分治法
class Solution { public class Status { public int lSum, rSum, mSum, iSum; public Status(int lSum, int rSum, int mSum, int iSum) { this.lSum = lSum; this.rSum = rSum; this.mSum = mSum; this.iSum = iSum; } } public int maxSubArray(int[] nums) { return getInfo(nums, 0, nums.length - 1).mSum; } public Status getInfo(int[] a, int l, int r) { if (l == r) { return new Status(a[l], a[l], a[l], a[l]); } int m = (l + r) >> 1; Status lSub = getInfo(a, l, m); Status rSub = getInfo(a, m + 1, r); return pushUp(lSub, rSub); } public Status pushUp(Status l, Status r) { int iSum = l.iSum + r.iSum; int lSum = Math.max(l.lSum, l.iSum + r.lSum); int rSum = Math.max(r.rSum, r.iSum + l.rSum); int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum); return new Status(lSum, rSum, mSum, iSum); } }时间复杂度：时间复杂度为 O(n) 空间复杂度：递归会使用 O(logn) 的栈空间，故渐进空间复杂度为 O(logn)
「方法二」相较于「方法一」来说，时间复杂度相同，但是因为使用了递归，并且维护了四个信息的结构体，运行的时间略长，空间复杂度也不如方法一优秀，而且难以理解。那么这种方法存在的意义是什么呢？
对于这道题而言，确实是如此的。但是仔细观察「方法二」，它不仅可以解决区间 [0, n - 1][0,n−1]，还可以用于解决任意的子区间 [l, r][l,r] 的问题。如果我们把 [0, n - 1][0,n−1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，即建成一颗真正的树之后，我们就可以在 O(logn) 的时间内求到任意区间内的答案，我们甚至可以修改序列中的值，做一些简单的维护，之后仍然可以在 O(logn) 的时间内求到任意区间内的答案，对于大规模查询的情况下，这种方法的优势便体现了出来。这棵树就是上文提及的一种神奇的数据结构——线段树。
