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 Two Non-Overlapping Subarrays

Number: 1096

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer array nums and two integers firstLen and secondLen, find the maximum sum of elements in two non-overlapping subarrays with lengths firstLen and secondLen. The two subarrays can appear in any order (firstLen subarray may come before or after secondLen subarray) but they should not overlap.

Key Insights

  • Use prefix sum to efficiently calculate the sum of any subarray.
  • Consider both orders: one where the first subarray comes before the second and vice versa.
  • For a fixed division, maintain a running maximum sum for the first subarray as you slide through the array.
  • The sliding window technique helps to compute subarray sums in O(1) time after an O(n) pre-computation.

Space and Time Complexity

Time Complexity: O(n) – We traverse the array a constant number of times. Space Complexity: O(n) – For storing the prefix sum array.

Solution

To solve the problem, we first precompute a prefix sum array so that any subarray sum can be obtained in constant time. Then we write a helper function that computes the maximum combined sum when one subarray (with length L) comes before the other (with length M).

The approach is to slide through the array:

  1. For each valid position for the subarray of length M, update the maximum sum of any subarray of length L that ends before the current M begins.
  2. Calculate the sum of the current M subarray.
  3. Combine the current best L subarray sum with the M subarray sum and update the answer.
  4. Finally, run this helper twice – once for the order (firstLen, secondLen) and once for (secondLen, firstLen) – and take the maximum.

This method ensures that the two subarrays do not overlap and that we always keep track of the best possible split.

Code Solutions

# Python solution for Maximum Sum of Two Non-Overlapping Subarrays

def maxSumTwoNoOverlap(nums, firstLen, secondLen):
    # Precompute prefix sums: prefix[i] is the sum of nums[0] to nums[i-1]
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
    
    # Helper function: L is the length of the first subarray, M is the length of the second subarray
    def helper(L, M):
        max_L = 0  # the best sum for subarray of length L seen so far
        best = 0
        # Start at index L+M, i is the end index (exclusive) for the M subarray.
        for i in range(L + M, n + 1):
            # Update best L subarray sum ending before the current M subarray starts:
            # Subarray for L ends at index i - M
            max_L = max(max_L, prefix[i - M] - prefix[i - M - L])
            # Sum for M subarray from i-M to i-1:
            current_M = prefix[i] - prefix[i - M]
            # Update global best
            best = max(best, max_L + current_M)
        return best

    # Return the maximum from both orders
    return max(helper(firstLen, secondLen), helper(secondLen, firstLen))

# Example usage:
# print(maxSumTwoNoOverlap([0,6,5,2,2,5,1,9,4], 1, 2))  # Output: 20
← Back to All Questions