[LintCode]Maximum Subarray II

类似max subarray I的解法，区别是我们这里扫两遍，从左边向右边的时候算出globalmax，从右边向左边的时候算出localMax，然后找两边加起来的最大值。首先我们定义两个变量，localMax[i]为以i结尾的subarray中最大的值，globalMax[i]定义为[0, i]范围中最大的subarray(subarray不一定需要以i结尾)。递推表达式是：

• localMax[i] = max(localMax[i - 1] + A[i], A[i]);
• globalMax[i] = max(globalMax[i - 1], localMax[i]);

从右边向左边的时候维护localMax[i]，这时的localMax[i]指的是以i开头的最大的subarray

• localMax[i] = max(localMax[i + 1] + A[i], A[i]);

扫两遍，时间复杂度O(n)，空间复杂度O(n)，从右边向左边扫的时候不需要开辟一个新的数组，并且计算最后最大值可以在第二次循环的时候一起做了，代码如下：

值得注意的是，从右边向左边扫的时候维护globalMax[i]也是可以，最后找到的最大值是一样的，不过这里维护localMa[i]就足够了，比如如果最大的结果是[x1, x2], [x3, x4]，那么当我们从右向左扫到x3的时候，[x1, x2]必定是左边一块的globalMax，如果不是的话就跟我们的假设矛盾了。另外指的注意的一点事分割的两个subarray是不允许有重叠的，也就是我们扫的时候左边和右边最后要留一个，否则没办法分割成两部分。