Maximum Sum of Two Non-Overlapping Subarrays

Naive Solution

A brute-force approach involves iterating through all possible subarrays of length firstLen and secondLen and checking if they are non-overlapping. We calculate the sum of each valid pair of subarrays and keep track of the maximum sum encountered.

Code (Python)

def max_sum_two_non_overlapping_subarrays_brute_force(nums, firstLen, secondLen):
    max_sum = 0
    n = len(nums)

    for i in range(n - firstLen + 1):
        for j in range(n - secondLen + 1):
            # Check if subarrays are non-overlapping
            if i + firstLen <= j or j + secondLen <= i:
                current_sum = sum(nums[i:i+firstLen]) + sum(nums[j:j+secondLen])
                max_sum = max(max_sum, current_sum)

    return max_sum

Time Complexity

O(N^2), where N is the length of the input array nums, because of the nested loops.

Space Complexity

O(1), as we only use a few variables to store the maximum sum and loop indices.

Optimal Solution

A more efficient approach uses prefix sums to calculate subarray sums in O(1) time. We can iterate through all possible split points and consider two cases: firstLen subarray comes before secondLen subarray and vice versa.

Algorithm

1. Calculate the prefix sum array to allow O(1) calculation of subarray sums.
2. Iterate through all possible starting positions for the firstLen subarray.
3. For each firstLen subarray, find the maximum sum of a secondLen subarray that doesn't overlap.
4. Repeat steps 2 and 3, but with the roles of firstLen and secondLen swapped.
5. Return the maximum sum found.

Code (Python)

def max_sum_two_non_overlapping_subarrays(nums, firstLen, secondLen):
    n = len(nums)

    # Calculate prefix sums
    prefix_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]

    def calculate_max_sum(firstLen, secondLen):
        max_sum = 0
        for i in range(firstLen, n - secondLen + 1):
            first_subarray_sum = prefix_sum[i] - prefix_sum[i - firstLen]
            
            # Find max second subarray sum before first subarray
            max_second_before = 0
            for k in range(secondLen, i - firstLen + 1):
                max_second_before = max(max_second_before, prefix_sum[i-firstLen] - prefix_sum[i-firstLen-secondLen])

            # Find max second subarray sum after first subarray
            max_second_after = 0
            for j in range(i + secondLen, n + 1):
                max_second_after = max(max_second_after, prefix_sum[j] - prefix_sum[j - secondLen])
            
            max_sum = max(max_sum, first_subarray_sum + max(max_second_before, max_second_after))
        
        return max_sum

    return max(calculate_max_sum(firstLen, secondLen), calculate_max_sum(secondLen, firstLen))

Optimized Code (Python)

def max_sum_two_non_overlapping_subarrays_optimized(nums, firstLen, secondLen):
    n = len(nums)
    prefix_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]

    def calculate_max_sum(firstLen, secondLen):
        max_sum = 0
        max_second_before = 0
        for i in range(firstLen + secondLen, n + 1):
            max_second_before = max(max_second_before, prefix_sum[i - firstLen] - prefix_sum[i - firstLen - secondLen])
            first_subarray_sum = prefix_sum[i] - prefix_sum[i - firstLen]
            max_sum = max(max_sum, first_subarray_sum + max_second_before)
        return max_sum

    return max(calculate_max_sum(firstLen, secondLen), calculate_max_sum(secondLen, firstLen))

Time Complexity

O(N), where N is the length of the input array nums. This is because we iterate through the array a constant number of times.

Space Complexity

O(N), for storing the prefix sum array.

Edge Cases

• If nums is empty or firstLen + secondLen > len(nums), return 0 (or handle the error appropriately).
• If firstLen or secondLen is 0 or negative, raise an exception or return an appropriate error value.
• If all elements in nums are negative, the function should still return the maximum possible sum (which may be negative).