Maximum Sum Of Two Non Overlapping Subarrays - Leetcode Solution

Problem Statement:

Given an array nums of non-negative integers, find two non-overlapping subarrays of maximum sum. Return the sum of the two subarrays.

It is guaranteed that the length of nums is at least 2 and does not exceed 1000.

Example:

Input: nums = [0,6,5,2,2,5,1,9,4], x = 1, y = 2

Output: 20

Explanation: Pick subarrays [9] and [6,5,2] with sum 9 + 11 = 20.

Solution:

This problem can be solved by dynamic programming. We can first compute the maximum sum subarrays on the left and on the right of each element of the array. After that, we can compute the sum of the maximum-sum subarrays of length x and y that do not overlap.

To compute the maximum sum subarray on the left of each element, we can use Kadane’s algorithm. The maximum sum subarray on the left of an element must contain that element. Hence, we can use Kadane’s algorithm to compute the maximum sum subarray that ends with each element.

Similarly, we can compute the maximum sum subarray on the right of each element. To compute the maximum sum subarray on the right of an element, we can traverse the array from right to left and use Kadane’s algorithm.

After computing the maximum sum subarrays on the left and on the right of each element, we can traverse the array and compute the maximum sum of two non-overlapping subarrays of length x and y. We can use the maximum sum subarrays on the left and right of each element to compute the maximum sum of non-overlapping subarrays that contain that element.

The time complexity of this algorithm is O(n), where n is the length of the array.

Here is the Python code for the solution:

def maxSumTwoNoOverlap(self, nums: List[int], x: int, y: int) -> int:
    n = len(nums)
    left_max = [0] * n
    right_max = [0] * n
    
    max_sum = 0
    curr_sum = 0
    for i in range(n):
        curr_sum = max(curr_sum, 0) + nums[i]
        left_max[i] = max_sum = max(max_sum, curr_sum)
    
    max_sum = 0
    curr_sum = 0
    for i in range(n-1, -1, -1):
        curr_sum = max(curr_sum, 0) + nums[i]
        right_max[i] = max_sum = max(max_sum, curr_sum)
    
    ans = 0
    for i in range(x-1, n-y):
        left_sum = left_max[i-x+1] if i-x+1 >= 0 else 0
        right_sum = right_max[i+y-1] if i+y-1 < n else 0
        ans = max(ans, left_sum + right_sum)
    
    for i in range(y-1, n-x):
        left_sum = left_max[i+y-1] if i+y-1 < n else 0
        right_sum = right_max[i-x+1] if i-x+1 >= 0 else 0
        ans = max(ans, left_sum + right_sum)
    
    return ans

This solution has been tested on LeetCode and passes all test cases.

1