https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/
def maxSum(nums, k):
n = len(nums)
maxval = 0
sums = []
res = [0, 0, 0]
for i in range(len(nums)):
if i == 0:
sums.append(nums[i])
else:
sums.append(sums[-1] + nums[i])
left = [0] * n
right = [n - k] * n
total = sums[k - 1]
for i in range(k, n):
if sums[i] - sums[i - k] > total:
left[i] = i - k + 1
total = sums[i] - sums[i - k]
else:
left[i] = left[i - 1]
total = sums[n - 1] - sums[n - k - 1]
for j in range(n - k - 1, -1, -1):
if sums[j + k - 1] - sums[j - 1] >= total:
right[j] = j
total = sums[j + k - 1] - sums[j - 1]
else:
right[j] = j + 1
for i in range(k, n - 2 * k + 1):
l, r = left[i - 1], right[i + k]
leftsum = sums[l + k - 1] - sums[l - 1] if l > 0 else 0
midsum = sums[i + k - 1] - sums[i - 1]
rightsum = sums[r + k - 1] - sums[r - 1]
total = leftsum + midsum + rightsum
if maxval < total:
maxval = max(maxval, total)
res = [l, i, r]
return res
