# 689. Maximum Sum of 3 Non-Overlapping Subarrays 三个无重叠子数组的最大和

## # 题目描述：

In a given array `nums` of positive integers, find three non-overlapping subarrays with maximum sum.

Each subarray will be of size `k`, and we want to maximize the sum of all `3*k` entries.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example:

``````Input: [1,2,1,2,6,7,5,1], 2
Output: [0, 3, 5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.
``````

Note:

1. nums.length will be between 1 and 20000.
2. nums[i] will be between 1 and 65535.
3. k will be between 1 and floor(nums.length / 3).

## # 解题方法

left[i]表示在区间[0, i]范围内长度为k且和最大的子数组的起始位置

right[i]表示在区间[i, n - 1]范围内长度为k且和最大的子数组的起始位置

left的求法是从左到右遍历，right的求法是从右到左遍历。遍历刚开始的K个位置内由于子数组长度小于k，所以left的值是0，right的值是N - k，代表的是能取子区间的边缘情况下索引。更新过程也不难，就是和已有的子数组最大和比较，然后更新索引位置就行了。

``````class Solution(object):
def maxSumOfThreeSubarrays(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
N = len(nums)
sums = [0]
left = [0] * N
right = [N - k] * N
mx = 0
res = [0, 0, 0]
for i, num in enumerate(nums):
sums.append(sums[-1] + num)
total = sums[k] - sums[0]
for i in range(k, N):
if sums[i + 1] - sums[i - k + 1] > total:
left[i] = i - k + 1
total = sums[i + 1] - sums[i - k + 1]
else:
left[i] = left[i - 1]
total = sums[N] - sums[N - k]
for j in range(N - k - 1, -1, -1):
if sums[j + k] - sums[j] >= total:
right[j] = j
total = sums[j + k] - sums[j]
else:
right[j] = right[j + 1]
for i in range(k, N - 2 * k + 1):
l, r = left[i - 1], right[i + k]
total = (sums[i + k] - sums[i]) + (sums[l + k] - sums[l]) + (sums[r + k] - sums[r])
if total > mx:
mx = max(mx, total)
res = [l, i, r]
return res
``````

https://www.cnblogs.com/grandyang/p/8453386.html

## # 日期

2018 年 10 月 5 日 —— 转眼假期要结束了！！