[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)，代码如下：