[LeetCode]Maximum Sum of 3 Non-Overlapping Subarrays

这道题和其他类似的题目的做法是一样的，都是分割数组。我们需要分别记录从左到右和从右到左的max subarray的所在位置，假设输入数组长度为n：

• left[i]表示从0到i为止，长度为k的max subarray的结尾位置
• right[i]表示从i到n - 1，长度为k的max subarray的起始位置

值记录位置的话，我们还需要办法取得区间和，这里很显然为了常数时间计算出给定区间的和，我们需要用presum数组。presums[i]代表前i个数的和，这样的话，我们有递推公式：

• left[i] = i, if presums[i + 1] - presums[i + 1 - k] > presums[left[i - 1] + 1] - presums[left[i - 1] - k + 1]
• else, left[i] = left[i - 1]
• right[i] = i, if presums[i + k] - presums[i] >= presums[right[i + 1] + k] - presums[right[i + 1]]
• else right[i] = right[i + 1]

left和right数组我们从左向右，从右向左一共扫两遍即可建立。剩下的我们只需要枚举中间的数组，然后算最大值即可。注意枚举中间数组的时候要个left和right数组留下至少k的空间。时间空间复杂度均为O(N)，代码如下：

	class Solution {
	public:
	vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
	int len = nums.size();
	if(len < 3 * k)return {};
	//store index, use presum to get the value
	vector<int> left(len, -1), right(len, -1), presums(len + 1, 0);
	int sum = 0;
	//init presum
	for(int i = 0; i < len; ++i)
	{
	sum += nums[i];
	presums[i + 1] = sum;
	}
	//left to right
	for(int i = k - 1; i < len; ++i)
	{
	if(i == k - 1){left[i] = i; continue;}
	int currSum = presums[i + 1] - presums[i + 1 - k];
	int currMax = presums[left[i - 1] + 1] - presums[left[i - 1] + 1 - k];
	left[i] = currSum > currMax? i : left[i - 1];
	}
	//right to left
	for(int i = len - k; i >= 0; --i)
	{
	if(i == len - k){right[i] = i; continue;}
	int currSum = presums[i + k] - presums[i];
	int currMax = presums[right[i + 1] + k] - presums[right[i + 1]];
	right[i] = currSum >= currMax? i: right[i + 1];
	}
	//middle
	int maxVal = INT_MIN;
	vector<int> res;
	for(int i = 2 * k - 1; i < len - k; ++i)
	{
	int leftIdx = left[i - k], rightIdx = right[i + 1];
	int leftSum = presums[leftIdx + 1] - presums[leftIdx + 1 - k];
	int rightSum = presums[rightIdx + k] - presums[rightIdx];
	int middle = presums[i + 1] - presums[i + 1 - k];
	int currSum = leftSum + middle + rightSum;
	if(currSum > maxVal)
	{
	maxVal = currSum;
	res = {leftIdx - k + 1, i - k + 1, rightIdx};
	}
	}
	return res;
	}
	};

view raw Maximum Sum of 3 Non-Overlapping Subarrays.cpp hosted with ❤ by GitHub