Maximum Sum of Two Non-Overlapping Subarrays

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.

• 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).

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)).

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;
    }
}