We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Sum of 3 Non-Overlapping Subarrays

Number: 689

Difficulty: Hard

Paid? No

Companies: Meta, Google, Bloomberg, Amazon

Problem Description

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k that have the maximum total sum. Return their starting indices as a list. If multiple answers exist, return the lexicographically smallest one.

Key Insights

  • Use a sliding window to compute the sum of every contiguous subarray of length k.
  • Precompute best left-window indices and best right-window indices for every possible middle window position.
  • Use dynamic programming: • left[i] stores the index of the subarray with the maximum sum for windows ending at or before i. • right[i] stores the index of the subarray with the maximum sum for windows starting at or after i.
  • Iterate over all possible middle subarray positions and combine with left and right indices to get the overall maximum sum while ensuring non-overlap.
  • Choosing indices with strict comparisons will naturally cater to the lexicographical requirement.

Space and Time Complexity

Time Complexity: O(n) – where n is the length of nums, since we scan the array a constant number of times. Space Complexity: O(n) – used for storing window sums and the left/right index arrays.

Solution

We first calculate the sum for every window of length k using a sliding window technique. Next, we build two auxiliary arrays: • The left array holds at each position the best starting index for a window on the left side. • The right array holds at each position the best starting index for a window on the right side. Then, for each possible middle window, we determine the best left and right windows and update the result if a higher total sum is achieved. This method ensures non-overlapping intervals and the lexicographically smallest result in case of ties.

Code Solutions

# Python solution with detailed comments

class Solution:
    def maxSumOfThreeSubarrays(self, nums, k):
        n = len(nums)
        window_sums = [0] * (n - k + 1)
        current_sum = sum(nums[:k])
        window_sums[0] = current_sum
        
        # Compute sums for each window of length k using sliding window technique
        for i in range(1, n - k + 1):
            current_sum += nums[i + k - 1] - nums[i - 1]
            window_sums[i] = current_sum
        
        left = [0] * len(window_sums)
        best_left = 0
        # Build left array, storing the index of best window sum up to each index
        for i in range(len(window_sums)):
            if window_sums[i] > window_sums[best_left]:
                best_left = i
            left[i] = best_left
        
        right = [0] * len(window_sums)
        best_right = len(window_sums) - 1
        # Build right array, ensuring lexicographical order (choose smaller index for tie)
        for i in range(len(window_sums) - 1, -1, -1):
            if window_sums[i] >= window_sums[best_right]:
                best_right = i
            right[i] = best_right

        max_total, ans = 0, None
        # Evaluate all possible middle intervals
        for mid in range(k, len(window_sums) - k):
            left_index = left[mid - k]
            right_index = right[mid + k]
            total = window_sums[left_index] + window_sums[mid] + window_sums[right_index]
            if total > max_total:
                max_total = total
                ans = [left_index, mid, right_index]
        return ans

# Example usage:
# sol = Solution()
# print(sol.maxSumOfThreeSubarrays([1,2,1,2,6,7,5,1], 2))
← Back to All Questions