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