Maximum Sum of Two Non-Overlapping Subarrays

Problem

Given an integer array nums and two integers firstLen and secondLen, return _the maximum sum of elements in two non-overlappingsubarrays with lengths _firstLen andsecondLen.

The array with length firstLen could occur before or after the array with length secondLen, but they have to be non-overlapping.

A subarray is a contiguous part of an array.

Examples

Example 1

1
2
3


Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20
Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.

Example 2

1
2
3


Input: nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
Output: 29
Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.

Example 3

1
2
3


Input: nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
Output: 31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [0,3,8] with length 3.

Constraints

1 <= firstLen, secondLen <= 1000
2 <= firstLen + secondLen <= 1000
firstLen + secondLen <= nums.length <= 1000
0 <= nums[i] <= 1000

Solution

Method 1 – Sliding Window for Both Orders

Intuition

To maximize the sum of two non-overlapping subarrays, try both possible orders: firstLen before secondLen and secondLen before firstLen. For each order, use sliding windows to track the best sum for the first subarray and combine it with the current sum of the second subarray.

Approach

For both orders (firstLen before secondLen and vice versa):
- Use a sliding window to compute the sum of the first subarray and keep track of the maximum sum so far.
- For each position, compute the sum of the second subarray and add the best sum of the first subarray that does not overlap.
Return the maximum sum found among both orders.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        return max(helper(nums, firstLen, secondLen), helper(nums, secondLen, firstLen));
    }
    int helper(vector<int>& nums, int l, int r) {
        int n = nums.size(), ans = 0, maxL = 0, sumL = 0, sumR = 0;
        for (int i = 0; i < l + r; ++i) sumR += nums[i];
        for (int i = 0; i < l; ++i) sumL += nums[i];
        maxL = sumL;
        for (int i = l; i < l + r; ++i) sumR += nums[i] - nums[i - r];
        ans = max(ans, maxL + sumR);
        for (int i = l + r; i < n; ++i) {
            sumL += nums[i - r] - nums[i - r - l];
            maxL = max(maxL, sumL);
            sumR += nums[i] - nums[i - r];
            ans = max(ans, maxL + sumR);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func maxSumTwoNoOverlap(nums []int, firstLen, secondLen int) int {
    return max(helper(nums, firstLen, secondLen), helper(nums, secondLen, firstLen))
}
func helper(nums []int, l, r int) int {
    n := len(nums)
    maxL, sumL, sumR, ans := 0, 0, 0, 0
    for i := 0; i < l; i++ { sumL += nums[i] }
    for i := l; i < l+r; i++ { sumR += nums[i] }
    maxL = sumL
    ans = max(ans, maxL+sumR)
    for i := l + r; i < n; i++ {
        sumL += nums[i-r] - nums[i-r-l]
        maxL = max(maxL, sumL)
        sumR += nums[i] - nums[i-r]
        ans = max(ans, maxL+sumR)
    }
    return ans
}
func max(a, b int) int { if a > b { return a }; return b }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        return Math.max(helper(nums, firstLen, secondLen), helper(nums, secondLen, firstLen));
    }
    private int helper(int[] nums, int l, int r) {
        int n = nums.length, ans = 0, maxL = 0, sumL = 0, sumR = 0;
        for (int i = 0; i < l; ++i) sumL += nums[i];
        for (int i = l; i < l + r; ++i) sumR += nums[i];
        maxL = sumL;
        ans = Math.max(ans, maxL + sumR);
        for (int i = l + r; i < n; ++i) {
            sumL += nums[i - r] - nums[i - r - l];
            maxL = Math.max(maxL, sumL);
            sumR += nums[i] - nums[i - r];
            ans = Math.max(ans, maxL + sumR);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
    fun maxSumTwoNoOverlap(nums: IntArray, firstLen: Int, secondLen: Int): Int {
        fun helper(l: Int, r: Int): Int {
            val n = nums.size
            var maxL = 0; var sumL = 0; var sumR = 0; var ans = 0
            for (i in 0 until l) sumL += nums[i]
            for (i in l until l + r) sumR += nums[i]
            maxL = sumL
            ans = maxOf(ans, maxL + sumR)
            for (i in l + r until n) {
                sumL += nums[i - r] - nums[i - r - l]
                maxL = maxOf(maxL, sumL)
                sumR += nums[i] - nums[i - r]
                ans = maxOf(ans, maxL + sumR)
            }
            return ans
        }
        return maxOf(helper(firstLen, secondLen), helper(secondLen, firstLen))
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def maxSumTwoNoOverlap(self, nums: list[int], firstLen: int, secondLen: int) -> int:
        def helper(l: int, r: int) -> int:
            n = len(nums)
            maxL = sumL = sumR = ans = 0
            sumL = sum(nums[:l])
            sumR = sum(nums[l:l+r])
            maxL = sumL
            ans = max(ans, maxL + sumR)
            for i in range(l + r, n):
                sumL += nums[i - r] - nums[i - r - l]
                maxL = max(maxL, sumL)
                sumR += nums[i] - nums[i - r]
                ans = max(ans, maxL + sumR)
            return ans
        return max(helper(firstLen, secondLen), helper(secondLen, firstLen))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


impl Solution {
    pub fn max_sum_two_no_overlap(nums: Vec<i32>, first_len: i32, second_len: i32) -> i32 {
        fn helper(nums: &Vec<i32>, l: usize, r: usize) -> i32 {
            let n = nums.len();
            let mut max_l = 0;
            let mut sum_l = nums.iter().take(l).sum::<i32>();
            let mut sum_r = nums.iter().skip(l).take(r).sum::<i32>();
            let mut ans = max_l + sum_r;
            max_l = sum_l;
            for i in l + r..n {
                sum_l += nums[i - r] - nums[i - r - l];
                max_l = max_l.max(sum_l);
                sum_r += nums[i] - nums[i - r];
                ans = ans.max(max_l + sum_r);
            }
            ans
        }
        let n = nums.len();
        let a = helper(&nums, first_len as usize, second_len as usize);
        let b = helper(&nums, second_len as usize, first_len as usize);
        a.max(b)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    maxSumTwoNoOverlap(nums: number[], firstLen: number, secondLen: number): number {
        function helper(l: number, r: number): number {
            let n = nums.length, maxL = 0, sumL = 0, sumR = 0, ans = 0;
            sumL = nums.slice(0, l).reduce((a, b) => a + b, 0);
            sumR = nums.slice(l, l + r).reduce((a, b) => a + b, 0);
            maxL = sumL;
            ans = Math.max(ans, maxL + sumR);
            for (let i = l + r; i < n; ++i) {
                sumL += nums[i - r] - nums[i - r - l];
                maxL = Math.max(maxL, sumL);
                sumR += nums[i] - nums[i - r];
                ans = Math.max(ans, maxL + sumR);
            }
            return ans;
        }
        return Math.max(helper(firstLen, secondLen), helper(secondLen, firstLen));
    }
}

Complexity

⏰ Time complexity: O(n), where n is the length of nums. Each window is scanned once.
🧺 Space complexity: O(1), only a few variables are used.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Sliding Window for Both Orders#

Intuition#

Approach#

Code#

Complexity#