Course4all
Join us on telegram
Home/dsa/Arrays & Hashing/Maximum Sum of Two Non-Overlapping Subarrays

Maximum Sum of Two Non-Overlapping Subarrays

Master this topic with zero to advance depth.

Maximum Sum of Two Non-Overlapping Subarrays

To find two non-overlapping subarrays with lengths L and M that give the maximum sum, we consider two cases: subarray L comes before M, or M comes before L. We use prefix sums to calculate subarray sums in O(1) and track the maximum sum seen so far.

Given an integer array nums and two integers firstLen and secondLen, return the maximum sum of two non-overlapping subarrays with lengths firstLen and secondLen. The subarrays must be non-overlapping, meaning they don't share any index.

Visual Representation

nums = [0, 6, 5, 2, 2, 5, 1, 9, 4], firstLen = 1, secondLen = 2 Possible Selections: [6] and [1, 9] -> Sum = 6 + 10 = 16 [0] and [9, 4] -> Sum = 0 + 13 = 13 [9] and [6, 5] -> Sum = 9 + 11 = 20 (MAX!)
Medium

Examples

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20

One choice of subarrays is [9] with length 1, and [6,5] with length 2.

Input: nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
Output: 29

One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.

Approach 1

Level I: Brute Force (Iterate All Subarrays)

Intuition

Iterate through all possible start positions for the first subarray of length firstLen. For each position, iterate through all possible start positions for the second subarray of length secondLen. Check if the two subarrays overlap; if not, calculate their sum and update the maximum.

⏱ O(N² * (L+M)) where N is array length, L and M are subarray lengths, due to repeated sum calculation.💾 O(1) extra space.

Detailed Dry Run

Sub1 (L=1)Sub2 (M=2)Total SumMax
[9] at i=7[0,6] at j=09+11=2020
[9] at i=7[4] at j=8OOB20
java
public class Main {
    public static int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int maxTotal = 0;
        int n = nums.length;
        for (int i = 0; i <= n - firstLen; i++) {
            int sum1 = 0;
            for (int k = 0; k < firstLen; k++) sum1 += nums[i + k];
            for (int j = 0; j <= n - secondLen; j++) {
                if (j + secondLen <= i || j >= i + firstLen) {
                    int sum2 = 0;
                    for (int l = 0; l < secondLen; l++) sum2 += nums[j + l];
                    maxTotal = Math.max(maxTotal, sum1 + sum2);
                }
            }
        }
        return maxTotal;
    }
    public static void main(String[] args) {
        int[] nums = {0,6,5,2,2,5,1,9,4};
        System.out.println(maxSumTwoNoOverlap(nums, 1, 2)); // Output: 20
    }
}
Approach 2

Level II: Better Solution (Prefix Sum + Nested Loops)

Intuition

Use prefix sums to calculate any subarray sum in O(1) time. This eliminates the inner loop for sum calculation but still requires O(N²) to check all pairs of non-overlapping subarrays.

⏱ O(N²) to iterate all pairs of subarray starting positions.💾 O(N) for the prefix sum array.

Detailed Dry Run

prefix[i+L]-prefix[i]prefix[j+M]-prefix[j]Action
sum(1) = 9sum(2) = 11total = 20
sum(1) = 4sum(2) = 10total = 14
java
public class Main {
    public static int maxSumTwoNoOverlap(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 maxTotal = 0;
        for (int i = 0; i <= n - L; i++) {
            int sumL = prefix[i + L] - prefix[i];
            for (int j = 0; j <= n - M; j++) {
                if (j + M <= i || j >= i + L) {
                    int sumM = prefix[j + M] - prefix[j];
                    maxTotal = Math.max(maxTotal, sumL + sumM);
                }
            }
        }
        return maxTotal;
    }
    public static void main(String[] args) {
        int[] nums = {3,8,1,3,2,1,8,9,0};
        System.out.println(maxSumTwoNoOverlap(nums, 3, 2)); // Output: 29
    }
}
Approach 3

Level III: Optimal Solution (Prefix Sum + Sliding Window)

Intuition

Maintain the maximum sum of a subarray of length L seen so far as we iterate through possible positions of a following subarray of length M. We repeat this with L following M to cover both cases. This gives O(N) by visiting each element once.

⏱ O(N) single pass for each of the two cases.💾 O(N) for prefix sums (can be O(1) with optimized sliding window).

Detailed Dry Run

Sliding Window Max Sum (L=1, M=2)

nums = [0, 6, 5, 2, 2, 5]

Pass 1 (L before M): [0] [6, 5] 2 2 5 -> sumL=0, maxL=0, sumM=11, res=11 0 [6] [5, 2] 2 5 -> sumL=6, maxL=6, sumM=7, res=max(11, 13)=13 0 6 [5] [2, 2] 5 -> sumL=5, maxL=6, sumM=4, res=max(13, 10)=13
java
public class Main {
    public static int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        return Math.max(
            helper(nums, firstLen, secondLen),
            helper(nums, secondLen, firstLen)
        );
    }
    
    private static int helper(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 maxFirst = 0;
        int result = 0;
        for (int i = firstLen; i <= n - secondLen; i++) {
            maxFirst = Math.max(maxFirst, prefix[i] - prefix[i - firstLen]);
            result = Math.max(result, maxFirst + (prefix[i + secondLen] - prefix[i]));
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {0,6,5,2,2,5,1,9,4};
        System.out.println(maxSumTwoNoOverlap(nums, 1, 2)); // Output: 20
    }
}
← Previous QuestionSet Matrix Zeroes
Next Question →Merge K Sorted Arrays