## 题目描述：

LeetCode 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:

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

## 解题思路：

```构造K项和数组sums，sums[i] = sum(nums[i - k + 1 .. i])

## Python代码：

``````class Solution(object):
def maxSumOfThreeSubarrays(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
size = len(nums)
nsize = size - k + 1
sums = [0] * nsize
maxa = [0] * nsize
maxb = [0] * nsize
total = 0
for x in range(size):
total += nums[x]
if x >= k - 1:
sums[x - k + 1] = total
total -= nums[x - k + 1]
maxn, maxi = 0, 0
for x in range(nsize):
if sums[x] > maxn:
maxn, maxi = sums[x], x
maxa[x] = (maxn, maxi)
maxn, maxi = 0, nsize - 1
for x in range(nsize - 1, -1, -1):
if sums[x] > maxn:
maxn, maxi = sums[x], x
maxb[x] = (maxn, maxi)
ansn, ansi = 0, None
for x in range(k, nsize - k):
va, ia = maxa[x - k]
vb, ib = maxb[x + k]
if sums[x] + va + vb > ansn:
ansn = sums[x] + va + vb
ansi = [ia, x, ib]
return ansi
``````

Pingbacks已关闭。