[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)，从右边向左边扫的时候不需要开辟一个新的数组，并且计算最后最大值可以在第二次循环的时候一起做了，代码如下：

	class Solution {
	public:
	/*
	* @param nums: A list of integers
	* @return: An integer denotes the sum of max two non-overlapping subarrays
	*/
	int maxTwoSubArrays(vector<int> &nums) {
	int len = nums.size(), localMax = INT_MIN;
	vector<int> dp(len, 0);
	//left to right
	for(int i = 0; i < len; ++i)
	{
	localMax = max(localMax, 0) + nums[i];
	dp[i] = i? max(dp[i - 1], localMax): localMax;
	}
	//right to left
	localMax = INT_MIN;
	int res = INT_MIN;
	for(int i = len - 1; i > 0; --i)
	{
	localMax = max(localMax, 0) + nums[i];
	res = max(localMax + dp[i - 1], res);
	}
	return res;
	}
	};

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

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