算法：42.最大子数组 II

https://www.lintcode.com/problem/maximum-subarray-ii/description

描述

给定一个整数数组，找出两个不重叠子数组使得它们的和最大。

每个子数组的数字在数组中的位置应该是连续的。

返回最大的和。

子数组最少包含一个数

样例

给出数组

这两个子数组分别为和或者和，它们的最大和都是

挑战

要求时间复杂度为 O(n)

思路

这个题目是在第一次完成 41 最大子数组 后隔了好久，将41题挑战目标完成了，45 最大子数组差 也想到办法了之后，这个题才想到办法的。

设立一个与输入数组大小相同的数组cache，然后从左往右依此遍历数组元素时，求出对应位置的最大子数组和的值，并保存在cache中。也就是说 cache[i] 中保存了输入数组 0 ～ i 的这一部分子数组的 最大子数组和。

然后再反向遍历一下，在反向遍历数组时将求出的右半部分数组的最大子数组和，与cache中的左半部分的最大子数组和 的和，记录下这个和的最大值，最后要求的结果就是这个和的最大值。

代码

在遍历数组求取 0～i 这部分的最大子数组和是一个迭代的过程，当i=0时，最大子数组和当然是 nums[0] （实际输入参数是List，用数组下标的方式表示），用maxSumIncludeLast记录包含上一个数组元素的子数组最大和，i=0时maxSumIncludeLast=nums[0]。当遍历到 i 的位置时，cache[i] 的计算方法为，先计算maxSumIncludeLast，然后 cache[i]取cache[i-1] 与lastMaxSubSum的最大值即可。

maxSumIncludeLast = maxSumIncludeLast>?(num+maxSumIncludeLast):num;的意思是如果包含了 nums[i-1] 的最大子数组和是个正值，那么包含 nums[i] 的值就是这个值加上 nums[i] 本身，如果包含了 nums[i-1] 的最大子数组和是负值，那么包含 nums[i] 的子数组的最大子数组和就是 nums[i] 。

反向遍历时也是同样道理计算右半部分的子数组的最大子数组和的最大值。cache[i]+cache[i+1]就是位置i处左右两边最大子数组和的和，找出这个和的最大值就是最后的结果。

小结

重点在于迭代过程的理解。理解了maxSumIncludeLast = maxSumIncludeLast>?(num+maxSumIncludeLast):num;这一句，其他的就容易理解了。

这是两个子数组和的情况，还有更高阶的43题，求k个子数组和。还未想到好办法。

一个子数组是用缓存，二个子数组是用左右划分，k个子数组该怎么办呢？