Maximum Sum Of 3 Non Overlapping Subarrays - Leetcode Solution

Problem Statement: Given an array nums of integers, find three non-overlapping subarrays with maximum sum.

Each of the three subarrays should be with a size of k, and we have to return the indexes of their starting position.

Return the result as an array of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example: Input: nums = [1,2,1,2,6,7,5,1], k = 2 Output: [0, 3, 5] Explanation:

• Subarrays: [1, 2], [2, 6], [7, 5]. The sum is 1+2+2+6+7+5=23.
• Expected output: starting indices 0, 3 and 5 of the subarrays respectively.

Solution Approach: The maximum sum of three non-overlapping subarrays can be easily solved by dynamic programming.

Let’s say that we have an array called sum, where sum[i] represents the sum of elements from the beginning of the array till index i.

To find the maximum sum of subarrays, we can use sliding windows of size k over the array, and store the current sum in another array called curr_sum.

Then, we need to find the maximum sum for each 3 non-overlapping subarrays of size k. This can be achieved by calculating 2 more arrays, left and right.

The left array will store the maximum sum of subarrays starting from the beginning of the array till index i, with every kth element included.

The right array will store the maximum sum of subarrays starting from the end of the array till index i, with every kth element included.

Finally, we can find the maximum sum of 3 non-overlapping subarrays by iterating over the array and calculating the sum of left[i-k], curr_sum[i], right[i+k] and storing the index where we found the maximum sum.

Algorithm:

• Construct a prefix array to keep track of the summation of the first k elements, then create the arrays left and right to maintain the maximum subarray sum from the beginning to the current point and from the end to the current point, respectively.
• Use sliding windows of size k to calculate current subarray sum that we will use to find the maximum sum of three non-overlapping subarrays.
• Iterate and find the maximum sum of three non-overlapping subarrays by iterating over the array and calculating the sum of left[i-k], curr_sum[i], right[i+k].
• Return the indices of the starting positions of the 3 subarrays.

Implementation:

def maxSumOfThreeSubarrays(nums, k):
    # Construct a prefix array to keep track of the summation of the first k elements
    n = len(nums)
    sum_num = [0] * (n + 1 )
    for i in range(1, n + 1 ):
        sum_num[i] = sum_num[i-1] + nums[i-1]
        
    # Create arrays left and right to maintain the maximum subarray sum 
    # from the beginning to the current point and from the end to the current point, respectively.
    left = [0] * n
    right = [n - k] * n
    for i in range(k, n):
        left[i] = left[i-1]
        if sum_num[i+1] - sum_num[i+1-k] > sum_num[left[i]+k] - sum_num[left[i]]:
            left[i] = i-k+1
        j = n-i-1
        right[j] = right[j+1]
        if sum_num[n-j] - sum_num[n-j+k] >= sum_num[right[j]] - sum_num[right[j]+k]:
            right[j] = j

    # Compute output based on left, right and the sliding window sum array.
    l, max_sum = 0, 0
    for i in range(k, n-k):
        j = left[i-k]
        r = right[i+k]
        curr_sum = sum_num[j+k] - sum_num[j] + sum_num[i+k] - sum_num[i] + sum_num[r+k] - sum_num[r]
        if curr_sum > max_sum:
            max_sum = curr_sum
            l = [j, i, r]
    return l

Complexity Analysis:

• Time Complexity: O(n)
• Space Complexity: O(n)

1