Maximum Sum of Two Non-Overlapping Subarrays - Video Solutions

Problem Overview: You are given an integer array and two lengths L and M. The task is to find two non-overlapping subarrays of these lengths whose combined sum is maximum. The order can be either L before M or M before L, but the subarrays must not overlap.

Approach 1: Prefix Sum and Sliding Window Technique (O(n) time, O(n) space)

This approach combines array prefix sums with a sliding window scan. First compute a prefix sum array so any subarray sum can be retrieved in O(1). Then iterate through the array while tracking the best possible subarray of length L seen so far before a window of length M. For each position, calculate the sum of the current M-length window and add it to the maximum L-length window found earlier. Repeat the process with the order reversed (M before L) because the larger result might come from either arrangement.

The key insight is that you never need to recompute previous windows. Instead, maintain a running maximum for the earlier window and update the answer while sliding the later window forward. This produces a linear scan of the array and avoids nested loops. Time complexity is O(n) and extra space is O(n) for the prefix sums (or O(1) if window sums are maintained incrementally).

Approach 2: Dynamic Programming Approach (O(n) time, O(n) space)

This approach uses dynamic programming to precompute the best subarray sums from both directions. Build two helper arrays: leftMax[i] stores the maximum sum of an L-length subarray ending at or before index i, and rightMax[i] stores the maximum sum of an M-length subarray starting at or after index i. These arrays allow you to combine non-overlapping segments efficiently.

After filling these arrays, iterate across the split point between the two subarrays. For every index, combine the best left segment with the best right segment. Run the same process again with L and M swapped to cover both possible orders. The DP arrays remove the need for recomputation and keep the algorithm linear.

This method is slightly more explicit than the sliding window technique because it stores intermediate results. It is useful when you want a clear separation between prefix computations and the final aggregation step.

Recommended for interviews: The prefix sum + sliding window solution is what most interviewers expect. It shows that you recognize the sliding window pattern and can optimize subarray calculations to O(n). Explaining the brute-force idea (checking all pairs of subarrays in O(n^2)) demonstrates understanding, but implementing the linear-time window technique shows strong problem-solving skills.