# Maximum Sum of Two Non-Overlapping Subarrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/maximum-sum-of-two-non-overlapping-subarrays
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
Given an integer array `nums` and two integers `firstLen` and `secondLen`, return _the maximum sum of elements in two non-overlapping **subarrays** with lengths_ `firstLen` _and_ `secondLen`.

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.

**Example 1:**

**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:**

**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:**

**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`

# Approaches
## Brute Force with Prefix Sums
This approach iterates through all possible pairs of non-overlapping subarrays. To make the calculation of subarray sums efficient, it first precomputes a prefix sum array.
**Time:** O(N^2), where N is the length of `nums`. We have two nested loops that iterate up to N. The prefix sum calculation takes `O(N)`. · **Space:** O(N) for the prefix sum array.
**Pros:** Simple to understand and implement.; Correctly explores all possibilities.
**Cons:** Inefficient due to the nested loops, leading to a quadratic time complexity which might be too slow for larger inputs.
### Explanation
First, we compute a prefix sum array, `prefix`, where `prefix[i]` is the sum of all elements from `nums[0]` to `nums[i-1]`. This allows us to calculate the sum of any subarray `nums[j...k]` in `O(1)` time as `prefix[k+1] - prefix[j]`. We then use two nested loops to consider every possible starting position for the first subarray (length `firstLen`) and the second subarray (length `secondLen`). Let the first subarray start at index `i` and the second at index `j`. Inside the loops, we check if the two subarrays are non-overlapping. The first subarray occupies indices `[i, i + firstLen - 1]` and the second occupies `[j, j + secondLen - 1]`. They are non-overlapping if the first one ends before the second one starts (`i + firstLen <= j`) or if the second one ends before the first one starts (`j + secondLen <= i`). If they are non-overlapping, we calculate their combined sum using the prefix sum array and update a `maxSum` variable if this sum is greater than the current maximum. After checking all pairs, `maxSum` will hold the result.

```java
class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int maxSum = 0;
        for (int i = 0; i <= n - firstLen; i++) {
            int sum1 = prefix[i + firstLen] - prefix[i];
            for (int j = 0; j <= n - secondLen; j++) {
                // Check for non-overlapping
                if (i + firstLen <= j || j + secondLen <= i) {
                    int sum2 = prefix[j + secondLen] - prefix[j];
                    maxSum = Math.max(maxSum, sum1 + sum2);
                }
            }
        }
        return maxSum;
    }
}
```
### Algorithm
- Get the length of the array, `n`.
- Create a prefix sum array `prefix` of size `n + 1`.
- Populate `prefix`: `prefix[i] = prefix[i-1] + nums[i-1]`.
- Initialize `maxSum = 0`.
- Loop `i` from `0` to `n - firstLen`:
    - Calculate `sum1 = prefix[i + firstLen] - prefix[i]`.
    - Loop `j` from `0` to `n - secondLen`:
        - Check for non-overlapping: `if (i + firstLen <= j || j + secondLen <= i)`.
        - If non-overlapping, calculate `sum2 = prefix[j + secondLen] - prefix[j]`.
        - Update `maxSum = max(maxSum, sum1 + sum2)`.
- Return `maxSum`.

## Dynamic Programming with Prefix Sums
This approach improves upon the brute force by avoiding redundant calculations. It breaks the problem into two cases: the first subarray appears before the second, and vice-versa. It then uses dynamic programming ideas to solve each case in linear time.
**Time:** O(N), where N is the length of `nums`. We make a single pass to compute prefix sums, and then two more passes inside the helper function. · **Space:** O(N) to store the prefix sum array.
**Pros:** Much more efficient than the brute-force approach with a linear time complexity.
**Cons:** Requires extra space for the prefix sum array.
### Explanation
The core idea is to solve two separate, symmetric problems and take the maximum of their results:
1. Max sum with a `firstLen` subarray appearing before a `secondLen` subarray.
2. Max sum with a `secondLen` subarray appearing before a `firstLen` subarray.

Let's focus on case 1. We can write a helper function `solve(L, M)` for this. We iterate through the array, considering each possible position for the `M`-length subarray. For each position, we need the maximum sum of an `L`-length subarray that appears entirely before it. To do this efficiently, as we iterate from left to right with a split point, we can keep track of the maximum `L`-length subarray sum seen so far to the left of the split point. We first compute a prefix sum array to get subarray sums in `O(1)`. The `solve(L, M)` function works as follows:
- Initialize `maxL` (max sum of an L-subarray) and `maxTotal`.
- Iterate `i` from `L + M` to `n`. The index `i` represents the end of the combined window.
- The `M`-length subarray ends at `i-1`. Its sum is `sumM`.
- The `L`-length subarray must end at or before `i - M - 1`. We update `maxL` by considering the new `L`-length subarray that just became available (the one ending at `i - M - 1`).
- We then update `maxTotal` with `maxL + sumM`.

The final result is `max(solve(firstLen, secondLen), solve(secondLen, firstLen))`.

```java
class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        return Math.max(
            findMaxSum(prefix, firstLen, secondLen),
            findMaxSum(prefix, secondLen, firstLen)
        );
    }

    private int findMaxSum(int[] prefix, int L, int M) {
        int n = prefix.length - 1;
        int maxL = 0;
        int maxTotal = 0;
        // Window of L+M, M is the second subarray
        for (int i = L + M; i <= n; i++) {
            // Max L-sum subarray in the first part [0, i-M-1]
            int sumL = prefix[i - M] - prefix[i - M - L];
            maxL = Math.max(maxL, sumL);
            
            // M-sum subarray in the second part [i-M, i-1]
            int sumM = prefix[i] - prefix[i - M];
            maxTotal = Math.max(maxTotal, maxL + sumM);
        }
        return maxTotal;
    }
}
```
### Algorithm
- Create a helper function `solve(prefix, L, M)`.
- Inside `solve`:
    - Initialize `maxLsum = 0` and `maxTotal = 0`.
    - Iterate `i` from `L + M` to `n`:
        - Calculate sum of L-subarray ending at `i - M - 1`: `sumL = prefix[i - M] - prefix[i - M - L]`.
        - Update `maxLsum = max(maxLsum, sumL)`.
        - Calculate sum of M-subarray ending at `i - 1`: `sumM = prefix[i] - prefix[i - M]`.
        - Update `maxTotal = max(maxTotal, maxLsum + sumM)`.
    - Return `maxTotal`.
- In the main function:
    - Calculate prefix sums for `nums`.
    - Call `res1 = solve(prefix, firstLen, secondLen)`.
    - Call `res2 = solve(prefix, secondLen, firstLen)`.
    - Return `max(res1, res2)`.

## Optimal Sliding Window
This is the most efficient approach, achieving linear time complexity with constant extra space. It builds upon the logic of the previous approach but eliminates the need for a prefix sum array by using sliding windows to calculate subarray sums on the fly.
**Time:** O(N), where N is the length of `nums`. The helper function is called twice, and each call involves a single pass through the array. · **Space:** O(1). We only use a few variables to store the running sums and maximums, independent of the input size.
**Pros:** Optimal solution with linear time and constant space complexity.
**Cons:** The logic can be slightly more complex to grasp initially compared to the prefix sum approach.
### Explanation
Similar to the DP approach, we solve for two cases: `firstLen` subarray before `secondLen`, and vice-versa. The final answer is the maximum of the two. Let's analyze the helper function `solve(L, M)` which finds the max sum with an `L`-length subarray before an `M`-length one, but this time without a prefix sum array. We maintain three key values: `sumL` (sum of the current `L`-length window), `sumM` (sum of the current `M`-length window), and `maxL` (the maximum `sumL` found so far). We initialize by calculating the sum of the first possible `L`-subarray (`nums[0...L-1]`) and the first possible `M`-subarray (`nums[L...L+M-1]`). This gives us our initial `maxL` and `maxTotal`. Then, we iterate from `i = L + M` to `n-1`. In each step, we slide both windows one position to the right. The `sumL` window is updated by subtracting the element that slides out and adding the new element that slides in. We then update `maxL` with the new `sumL`. The `sumM` window is also updated similarly. We then calculate the potential new max total sum: `maxL + sumM`, and update our overall `maxTotal` if it's larger. By doing this for both `(firstLen, secondLen)` and `(secondLen, firstLen)`, we find the global maximum.

```java
class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        return Math.max(
            solve(nums, firstLen, secondLen), 
            solve(nums, secondLen, firstLen)
        );
    }

    private int solve(int[] nums, int L, int M) {
        int n = nums.length;
        int sumL = 0;
        for (int i = 0; i < L; i++) {
            sumL += nums[i];
        }

        int sumM = 0;
        for (int i = L; i < L + M; i++) {
            sumM += nums[i];
        }

        int maxL = sumL;
        int maxTotal = sumL + sumM;

        for (int i = L + M; i < n; i++) {
            // Slide window for L
            sumL += nums[i - M] - nums[i - M - L];
            maxL = Math.max(maxL, sumL);
            
            // Slide window for M
            sumM += nums[i] - nums[i - M];
            
            maxTotal = Math.max(maxTotal, maxL + sumM);
        }
        return maxTotal;
    }
}
```
### Algorithm
- Create a helper function `solve(nums, L, M)`.
- Inside `solve`:
    - Initialize `sumL = 0` for the first `L` elements.
    - Initialize `sumM = 0` for the next `M` elements.
    - `maxL = sumL`.
    - `maxTotal = sumL + sumM`.
    - Iterate `i` from `L + M` to `n - 1`:
        - Update `sumL` by sliding the window: `sumL = sumL - nums[i - L - M] + nums[i - M]`.
        - Update `maxL = max(maxL, sumL)`.
        - Update `sumM` by sliding the window: `sumM = sumM - nums[i - M] + nums[i]`.
        - Update `maxTotal = max(maxTotal, maxL + sumM)`.
    - Return `maxTotal`.
- In the main function:
    - Call `res1 = solve(nums, firstLen, secondLen)`.
    - Call `res2 = solve(nums, secondLen, firstLen)`.
    - Return `max(res1, res2)`.

# Solutions
### Java

```java
class Solution {
public
  int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
    int n = nums.length;
    int[] s = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    int ans = 0;
    for (int i = firstLen, t = 0; i + secondLen - 1 < n; ++i) {
      t = Math.max(t, s[i] - s[i - firstLen]);
      ans = Math.max(ans, t + s[i + secondLen] - s[i]);
    }
    for (int i = secondLen, t = 0; i + firstLen - 1 < n; ++i) {
      t = Math.max(t, s[i] - s[i - secondLen]);
      ans = Math.max(ans, t + s[i + firstLen] - s[i]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxSumTwoNoOverlap(vector<int> &nums, int firstLen, int secondLen) {
    int n = nums.size();
    vector<int> s(n + 1);
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    int ans = 0;
    for (int i = firstLen, t = 0; i + secondLen - 1 < n; ++i) {
      t = max(t, s[i] - s[i - firstLen]);
      ans = max(ans, t + s[i + secondLen] - s[i]);
    }
    for (int i = secondLen, t = 0; i + firstLen - 1 < n; ++i) {
      t = max(t, s[i] - s[i - secondLen]);
      ans = max(ans, t + s[i + firstLen] - s[i]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int: n = len(nums) s = list(accumulate(nums, initial=0)) ans = t = 0 i = firstLen while i + secondLen - 1 < n: t = max(t, s[i] - s[i - firstLen]) ans = max(ans, t + s[i + secondLen] - s[i]) i += 1 t = 0 i = secondLen while i + firstLen - 1 < n: t = max(t, s[i] - s[i - secondLen]) ans = max(ans, t + s[i + firstLen] - s[i]) i += 1 return ans

```