Problem Description

Given an array of integers nums and two integers firstLen and secondLen, your task is to find two non-overlapping subarrays of lengths firstLen and secondLen such that the sum of their elements is maximized. The subarrays must not overlap, meaning no index is used in both subarrays. Return the maximum possible sum of these two subarrays.

• Each subarray must be of exact length firstLen and secondLen respectively.
• Subarrays can appear in any order (firstLen before secondLen or vice versa).
• All elements of nums are integers, and you must not reuse any element in both subarrays.
• There is always at least one valid solution.

Thought Process

At first glance, this problem looks similar to finding the maximum sum subarray, but with the added twist of needing two subarrays of specific lengths that do not overlap. A brute-force approach would be to try every possible pair of non-overlapping subarrays, but this would be too slow for large arrays.

To optimize, we need to efficiently compute the maximum sum of subarrays of fixed lengths as we traverse the array. By using prefix sums, we can quickly calculate the sum of any subarray. The key insight is to, for each possible split, keep track of the best subarray sum seen so far for one length, and combine it with the current subarray sum of the other length, considering both possible orders (firstLen before secondLen and vice versa).

This approach leverages dynamic programming principles and sliding window techniques to avoid redundant calculations and ensure we never pick overlapping subarrays.

Solution Approach

• Prefix Sums: Compute the prefix sum array so that the sum of any subarray can be found in constant time.
• Sliding Window: Use sliding windows to efficiently calculate the sum of subarrays of length firstLen and secondLen as we iterate.
• Track Maximums: As we go through the array, keep track of the maximum sum of a subarray of length firstLen seen so far, and then for each possible position of the secondLen subarray (after the first), calculate their sum. Do the same with the order reversed.
• Two Passes: For each possible arrangement (firstLen before secondLen, and secondLen before firstLen), perform a pass through the array, updating the result with the best possible combination found.
• Return the Maximum: The answer is the largest sum found from both arrangements.

This approach ensures we always respect the non-overlapping constraint and efficiently finds the optimal solution.

Example Walkthrough

Suppose nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2.

1. First, try firstLen before secondLen:
   • As we slide a window of length 1, we keep track of the best sum so far.
   • For each position where a window of length 2 could start after the first window, we compute their sum and update the result if it's better.
   • Example: If the best 1-length sum before index 2 is 6 (from index 1), and the 2-length sum at index 2 is 5+2=7, total is 13.
2. Then, try secondLen before firstLen:
   • Now, slide a window of length 2, and for each possible following window of length 1, compute the sum.
   • Example: Best 2-length sum before index 3 is 6+5=11, and 1-length sum at index 3 is 2, total is 13.
3. Result: The maximum sum found is 20 (from 9+4 and 6+5).

This process ensures we consider all valid, non-overlapping pairs and always find the maximum.

Time and Space Complexity

• Brute-Force Approach:
  • For each possible first subarray, try all possible non-overlapping second subarrays. This is O(N^2).
  • Not feasible for large arrays.
• Optimized Approach:
  • We traverse the array a constant number of times (for prefix sums and sliding windows), so the time complexity is O(N).
  • Space complexity is O(N) for the prefix sum array.

This optimization is possible due to the use of prefix sums and sliding windows, avoiding redundant calculations.

Summary

The key to solving the Maximum Sum of Two Non-Overlapping Subarrays problem efficiently is to combine prefix sums with sliding window techniques. By considering both possible orders of the subarrays and always tracking the best subarray sum so far, we can guarantee the optimal solution in linear time. This method elegantly avoids overlap and leverages dynamic programming principles, making it both efficient and easy to understand.

Code Implementation

def maxSumTwoNoOverlap(nums, firstLen, secondLen):
    def maxSum(L, M):
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + nums[i]
        maxL = res = 0
        for i in range(L + M, n + 1):
            maxL = max(maxL, prefix[i - M] - prefix[i - M - L])
            res = max(res, maxL + prefix[i] - prefix[i - M])
        return res
    return max(maxSum(firstLen, secondLen), maxSum(secondLen, firstLen))
      

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 M) {
        int n = nums.size();
        vector<int> prefix(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        int maxL = 0, res = 0;
        for (int i = L + M; i <= n; ++i) {
            maxL = max(maxL, prefix[i - M] - prefix[i - M - L]);
            res = max(res, maxL + prefix[i] - prefix[i - M]);
        }
        return res;
    }
};
      

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        return Math.max(maxSum(nums, firstLen, secondLen), maxSum(nums, secondLen, firstLen));
    }
    private int maxSum(int[] nums, int L, int M) {
        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 maxL = 0, res = 0;
        for (int i = L + M; i <= n; ++i) {
            maxL = Math.max(maxL, prefix[i - M] - prefix[i - M - L]);
            res = Math.max(res, maxL + prefix[i] - prefix[i - M]);
        }
        return res;
    }
}
      

var maxSumTwoNoOverlap = function(nums, firstLen, secondLen) {
    function maxSum(L, M) {
        const n = nums.length;
        const prefix = new Array(n + 1).fill(0);
        for (let i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        let maxL = 0, res = 0;
        for (let i = L + M; i <= n; ++i) {
            maxL = Math.max(maxL, prefix[i - M] - prefix[i - M - L]);
            res = Math.max(res, maxL + prefix[i] - prefix[i - M]);
        }
        return res;
    }
    return Math.max(maxSum(firstLen, secondLen), maxSum(secondLen, firstLen));
};