[LintCode]Maximum Subarray III

算是非常难的题目了，我们之前在Maximum Subarray II中的做法如果要generalize到k的解法，需要额外扫和空间，而且代码不优雅，这里我们的解法也是DP，逻辑上可能会有点绕，不过最后的解法会十分的clean，核心代码只有两行。

跟之前一样这里我们维护两个东西，localMax[i][j]为进行了i次partition前j个数字的最大subarray，并且最后一个subarray以A[j - 1](A为输入的数组)结尾；globalMax[i][j]为进行了i次partition前j个数字的最大subarray(最后一个subarray不一定需要以j - 1结尾)。类比之前的DP方程，我们推出新的DP方程：

• globalMax[i][j] = max(localMax[i][j], globalMax[i][j - 1])
• localMax[i][j] = max(globalMax[i - 1][k - 1] + sum(nums[k], nums[j - 1])), where i <= k < j

第一眼看上去对于第二个DP方程我们需要每次构建localMax[i][j]的时候把后面都扫一遍，这样总的复杂度会达到O(n^2)，但是我们有方法把这一步优化到O(n)。根据上面的递推公式，我们可以用localMax[i][j - 1]来推出localMax[i][j]:

• localMax[i][j] = max(localMax[i][j - 1], globalMax[i - 1][j - 1]) + nums[j - 1]

设想如下例子：

• globalMax[i - 1]: 3, 5, -1, 8, 7
• A[]:                      1, 2, 6, -2, 0

我们可以看到当算完A[2], localMax[i][2] = max(globalMax[i - 1][k] + sumFromTo(A[k + 1], A[j])) = 11。当我们算到A[3]的时候，如果我们不考虑新加的globalMax[i - 1][2] + A[3]的组合, 之前的所有组合（globalMax[i - 1][0] + sumFromTo(A[1], A[2]), globalMax[i - 1][1] + sumFromTo(A[2], A[2])）都只需要再加一个A[3]就是新的globalMax[i - 1][k] + sumFromTo(A[k + 1], A[j])的值，所以之前的最大的值，到新的还是原来所组合的最大值，只需要和新加的比一下就可以了。所以我们可以转化成上面的递推公式。
时间复杂度O(k * n)，空间复杂度O(k * n)，空间应该可以维护一个滚动数组来优化到n不过这道题的逻辑比较复杂，为了维护逻辑的清晰性，我们不优化空间。代码如下，我们可以看到代码中的27和28行就是我们DP方程的表示，核心代码只有这两行：