[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方程的表示，核心代码只有这两行：

	class Solution {
	public:
	/**
	* @param nums: A list of integers
	* @param k: An integer denote to find k non-overlapping subarrays
	* @return: An integer denote the sum of max k non-overlapping subarrays
	*/
	int maxSubArray(vector<int> &nums, int k) {
	int len = nums.size();
	if(len < k)return 0;
	//globalMax[i][j] represents max sum we have when doing k partitions with first j elements
	//localMax[i][j] represents max sum we have when doing k partitions with first j elements
	//and the last subarray ends at nums[j]
	//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
	//from the fomular above, we have
	//localMax[i][j] = max(localMax[i][j - 1], globalMax[i - 1][j - 1]) + nums[j - 1]
	//base case: globalMax[i][0] = 0, globalMax[0][j] = 0, localMax[i][0] = 0, localMax[0][j] = 0
	vector<vector<int>> globalMax(k + 1, vector<int>(len + 1, 0)), localMax(k + 1, vector<int>(len + 1, 0));
	for(int i = 1; i <= k ;++i)
	{
	//can't partite with less than i elemts
	for(int j = i; j <= len; ++j)
	{
	//make sure check the boudary otherwise default 0 may override negative value
	//for example: nums = {-1, 0 , 1}, k = 3
	localMax[i][j] = i == j? globalMax[i - 1][j - 1] + nums[j - 1] : max(localMax[i][j - 1], globalMax[i - 1][j - 1]) + nums[j - 1];
	globalMax[i][j] = j == i? localMax[i][j]: max(localMax[i][j], globalMax[i][j - 1]);
	}
	}
	return globalMax[k][len];
	}
	};

view raw Maximum Subarray III.cpp hosted with ❤ by GitHub