# 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.
# Solution
Approach 1: two pass for the array to record the max sum seen from the left, and from the right.
# Code (Python)
Approach 1:
def maxSumOfThreeSubarrays(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
# add self with next k-1 items
k_sum = [sum(nums[0:k])]
for i in range(1, len(nums) - k + 1):
k_sum.append(k_sum[-1] - nums[i-1] + nums[i+k-1])
# determine max up till num from left and right
max_before, max_after = [k_sum[0]], [k_sum[-1]]
argmax_before, argmax_after = [0], [len(k_sum) - 1]
for i in range(1, len(k_sum)):
max_before.append(max(max_before[-1], k_sum[i]))
argmax_before.append(argmax_before[-1] if max_before[-2] >= k_sum[i] else i)
for i in range(len(k_sum) - 2, -1, -1):
max_after.append(max(max_after[-1], k_sum[i]))
argmax_after.append(argmax_after[-1] if max_after[-2] >= k_sum[i] else i)
max_after.reverse()
argmax_after.reverse()
# calculate 3 sum at least k positions apart
args = [-1, -1, -1]
max_sum = -float('inf')
for mid in range(k, len(k_sum) - k):
new_sum = k_sum[mid] + max_before[mid-k] + max_after[mid+k]
if new_sum > max_sum:
max_sum = new_sum
args = [argmax_before[mid-k], mid, argmax_after[mid+k]]
return args
# Code (C++)
Approach 1:
Approach 2: