Maximum Sum of Non-Overlapping Subarrays

max_sum_of_three_subarrays.py

"""
Description:
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.
- 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).

Examples:
Input: nums=[1,2,1,2,6,7,5,1], k=2
Output: [0, 3, 5] -- subarrays are [1, 2], [2, 6], [7, 5]

Input: nums=[7,13,20,19,19,2,10,1,1,19], k=3
Output: [1, 4, 7] -- subarrays are [13, 20, 19], [19, 2, 10], [1, 1, 19]
"""

def maxSumOfThreeSubarrays(nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: List[int]
    """
    n = len(nums)
    # creates accumulation array, length n + 1
    acc = [0]
    for i in range(n):
        acc.append(acc[i] + nums[i])

    # left and right side of max sums
    total = acc[k] - acc[0]
    left, right = [0] * n, [0] * n
    for i in range(k, n-2*k+1):  # 2*k elements should be left
        if total < acc[i] - acc[i - k]:
            left[i] = i - k
            total = acc[i] - acc[i - k]
        else:
            left[i] = left[i - 1]
    total = acc[n] - acc[n - k]
    for i in range(n-k, 2*k-1, -1):
        if total <= acc[i + k] - acc[i]:
            right[i] = i
            total = acc[i + k] - acc[i]
        else:
            right[i] = right[i + 1]
    
    # find maximum combination starting from a middle
    maxSum = -1
    for i in range(k, n-2*k+1):
        l, r = left[i], right[i + k]
        total = (acc[i + k] - acc[i]) +\
                (acc[l + k] - acc[l]) +\
                (acc[r + k] - acc[r])
        if maxSum < total:
            maxSum = total
            result = (l, i, r)
    return result