1031. Maximum Sum of Two Non-Overlapping Subarrays

MediumArrayDynamic ProgrammingSliding Window
Leetcode Link

Problem Description

Given an array nums of integers and two distinct integer values firstLen and secondLen, the task is to find the maximum sum that can be achieved by taking two non-overlapping subarrays from nums, with one subarray having a length of firstLen and the other having a length of secondLen. A subarray is defined as a sequence of elements from the array that are contiguous (i.e., no gaps in between). It is important to note that the subarray with length firstLen can either come before or after the subarray with length secondLen, but they cannot overlap.

Intuition

To solve this problem, an effective idea is to utilize the concept of prefix sums to quickly calculate the sum of elements in any subarray of the given nums array. By using the prefix sums, you can determine the sum of elements in constant time, rather than recalculating it every time by adding up elements iteratively.

Here's the intuition broken down into steps:

  1. Calculate prefix sums: First, we need to create an array of prefix sums s from the input array nums, which holds the sum of the elements from the start up to the current index.

  2. Initialize variables: We then define two variables ans to store the maximum sum found so far and t to keep track of the maximum sum of subarrays of a particular length as we traverse the array.

  3. Find Maximum for each configuration:

    • Start by considering subarrays of length firstLen and then move on to subarrays of length secondLen. As we iterate through the array, we calculate the maximum sum of a firstLen subarray ending at the current index and store it in t.
    • Then we use this to calculate and update ans by adding the sum of the following secondLen subarray.
    • We ensure that at each step, the chosen subarrays do not overlap by controlling the indices and lengths properly.

  4. Repeat the process in reverse: To ensure we are not missing out on any configuration (since the firstLen subarray can appear before or after the secondLen subarray), we reverse the lengths and repeat the procedure.

  5. Return the result: The maximum of all calculated sums is stored in ans, which we return as the final answer.

By iterating over each possible starting point for the firstLen and secondLen subarrays and efficiently calculating sums using the prefix array, we find the maximum sum of two non-overlapping subarrays of designated lengths.

Learn more about Dynamic Programming and Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Solution Approach

The solution is built around the efficient use of a prefix sum array and two traversal patterns to evaluate all possible configurations of the two required subarrays.

Here are the steps involved in the implementation:

  1. Prefix Sum Array: A prefix sum array s is constructed from the input array nums using list(accumulate(nums, initial=0)). This function call essentially generates a new list where each element at index i represents the sum of the nums array up to that index.

  2. Traverse and Compute for firstLen and secondLen: The algorithm starts off with two for loop constructs, each responsible for handling one of the two configurations:

    • The first for loop starts iterating after firstLen to leave room for the first subarray. Inside this loop, t is calculated as the maximum sum of the firstLen subarray ending at the current index i.
    • It immediately computes the sum of the next secondLen subarray and updates the answer ans if needed, by adding the sum of the current firstLen subarray (t) and the sum of the consecutive secondLen subarray.

  3. Variable t and ans: The variable t tracks the maximum sum of a subarray of length firstLen found up to the current position in the iteration (essentially, it holds the best answer found so far for the left side). The variable ans accumulates the maximum combined sum of two non-overlapping subarrays, comparing the sum of the current subarray of firstLen plus the sum of the non-overlapping subarray of secondLen.

  4. Repeat the Process for Reversed Lengths: After the first pass is completed, the same process is repeated, with the roles of firstLen and secondLen reversed. This ensures that all possible positions of firstLen and secondLen subarrays are evaluated.

  5. Checking for Overlapping: While updating ans, care is taken to ensure that the subarrays do not overlap by controlling the sequence of index increments and subarray length considerations.

  6. Return the Maximum Sum: After both traversals, the variable ans holds the maximum sum possible without overlap, which is then returned.

By separately handling the cases for which subarray comes first, the function ensures it examines all possible configurations while efficiently computing sums using the prefix sum array, thus arriving at the correct maximum sum of two non-overlapping subarrays of given lengths.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Example Walkthrough

Let's walk through an example to illustrate the solution approach. Consider the array nums = [3, 5, 2, 1, 7, 3], with firstLen = 2 and secondLen = 3.

Step 1: Prefix Sum Array

Construct a prefix sum array s from nums.

  • Original nums array: [3, 5, 2, 1, 7, 3]
  • Prefix sum array s: [0, 3, 8, 10, 11, 18, 21]

The element at index i in the prefix sum array represents the sum of all elements in nums up to index i-1.

Step 2: Traverse and Compute for firstLen, then secondLen

  • Initialize ans to -infinity (or a very small number) and t to 0.
  • Start the first for loop after firstLen (index is 2 in this case).

Step 3: Variable t and ans

  • At index 2 (i = 2), we ignore because we cannot form both subarrays.
  • At index 3 (i = 3), t = max(t, s[3] - s[3 - firstLen]) which is max(0, 10 - 3) so t = 7.

We then calculate the sum of the next secondLen subarray: s[i + secondLen] - s[i] which is s[6] - s[3] so 18 - 10 = 8. Since 8 (secondLen subarray sum) + 7 (firstLen subarray sum) = 15 is greater than ans, we update ans to 15.

Step 4: Repeat for Reversed Lengths

  • We reset t to 0, and reverse the firstLen and secondLen.
  • Start the next for loop after secondLen (index is 3 in this case).
  • At index 3 (i = 3), we ignore because we cannot form both subarrays.

Checking for Overlapping

  • At index 4 (i = 4), t = max(t, s[4] - s[4 - secondLen]) which is max(0, 11 - 3) so t = 8.

We then compute the sum of the next firstLen subarray: s[i + firstLen] - s[i] which is s[6] - s[4] so 21 - 11 = 10. We add 10 (firstLen subarray sum) to 8 (secondLen subarray sum) and get 10 + 8 = 18 which is greater than ans, so we update ans to 18.

Step 6: Return the Maximum Sum

We have finished evaluating both configurations. The variable ans now holds the value 18, which is the maximum sum of two non-overlapping subarrays for the lengths provided. Thus, we return 18 as the final answer for this example.

Solution Implementation

1from itertools import accumulate
2
3class Solution:
4    def max_sum_two_no_overlap(self, nums: List[int], first_len: int, second_len: int) -> int:
5        # Determine the total number of elements in nums
6        n = len(nums)
7      
8        # Create a prefix sum array with an initial value of 0 for easier calculation
9        prefix_sums = list(accumulate(nums, initial=0))
10      
11        # Initialize the answer and a temporary variable for tracking the max sum of the first array
12        max_sum = max_sum_first_array = 0
13      
14        # Loop through nums to consider every possible second array starting from index first_len
15        i = first_len
16        while i + second_len - 1 < n:
17            # Find the max sum of the first array ending before the start of the second array
18            max_sum_first_array = max(max_sum_first_array, prefix_sums[i] - prefix_sums[i - first_len])
19            # Update the max_sum with the best we've seen combining the two arrays so far
20            max_sum = max(max_sum, max_sum_first_array + prefix_sums[i + second_len] - prefix_sums[i])
21            i += 1
22
23        # Reset the temporary variable for the max sum of first and second arrays
24        max_sum_second_array = 0
25        # Loop through nums to consider every possible first array starting from index second_len
26        i = second_len
27        while i + first_len - 1 < n:
28            # Find the max sum of the second array ending before the start of the first array
29            max_sum_second_array = max(max_sum_second_array, prefix_sums[i] - prefix_sums[i - second_len])
30            # Update the max_sum with the best we've seen for the swapped sizes of the two arrays
31            max_sum = max(max_sum, max_sum_second_array + prefix_sums[i + first_len] - prefix_sums[i])
32            i += 1
33      
34        # Return the maximum sum found
35        return max_sum
36
1class Solution {
2    public int maxSumTwoNoOverlap(int[] numbers, int firstLength, int secondLength) {
3        // Initialize the length of the array
4        int arrayLength = numbers.length;
5        // Create a prefix sum array with an additional 0 at the beginning
6        int[] prefixSums = new int[arrayLength + 1];
7        // Calculate prefix sums
8        for (int i = 0; i < arrayLength; ++i) {
9            prefixSums[i + 1] = prefixSums[i] + numbers[i];
10        }
11      
12        // Initialize the answer to be the maximum sum we are looking for
13        int maxSum = 0;
14      
15        // First scenario: firstLength subarray is before secondLength subarray
16        // Loop from firstLength up to the point where a contiguous secondLength subarray can fit
17        for (int i = firstLength, tempMax = 0; i + secondLength - 1 < arrayLength; ++i) {
18            // Get the maximum sum of any firstLength subarray up to the current index
19            tempMax = Math.max(tempMax, prefixSums[i] - prefixSums[i - firstLength]);
20            // Update the maxSum with the sum of the maximum firstLength subarray and the contiguous secondLength subarray
21            maxSum = Math.max(maxSum, tempMax + prefixSums[i + secondLength] - prefixSums[i]);
22        }
23      
24        // Second scenario: secondLength subarray is before firstLength subarray
25        // Loop from secondLength up to the point where a contiguous firstLength subarray can fit
26        for (int i = secondLength, tempMax = 0; i + firstLength - 1 < arrayLength; ++i) {
27            // Get the maximum sum of any secondLength subarray up to the current index
28            tempMax = Math.max(tempMax, prefixSums[i] - prefixSums[i - secondLength]);
29            // Update the maxSum with the sum of the maximum secondLength subarray and the contiguous firstLength subarray
30            maxSum = Math.max(maxSum, tempMax + prefixSums[i + firstLength] - prefixSums[i]);
31        }
32      
33        // Return the maximum sum found for both scenarios
34        return maxSum;
35    }
36}
37
1#include <vector>
2#include <algorithm> // For std::max
3
4using std::vector;
5using std::max;
6
7class Solution {
8public:
9    int maxSumTwoNoOverlap(vector<int>& nums, int L, int M) {
10        int n = nums.size();
11        vector<int> prefixSum(n + 1, 0);
12        // Calculate prefix sums
13        for (int i = 0; i < n; ++i) {
14            prefixSum[i + 1] = prefixSum[i] + nums[i];
15        }
16
17        int maxSum = 0;
18        int maxL = 0; // To store max sum of subarray with length L
19
20        // Find max sum for two non-overlapping subarrays
21        // where first subarray has length L and second has length M
22        for (int i = L; i + M - 1 < n; ++i) {
23            maxL = max(maxL, prefixSum[i] - prefixSum[i - L]);
24            maxSum = max(maxSum, maxL + prefixSum[i + M] - prefixSum[i]);
25        }
26
27        int maxM = 0; // To store max sum of subarray with length M
28
29        // Same as above, but first subarray has length M and second has length L
30        for (int i = M; i + L - 1 < n; ++i) {
31            maxM = max(maxM, prefixSum[i] - prefixSum[i - M]);
32            maxSum = max(maxSum, maxM + prefixSum[i + L] - prefixSum[i]);
33        }
34
35        // Return the max possible sum of two non-overlapping subarrays
36        return maxSum;
37    }
38};
39
1// The `nums` array stores the integers, `L` and `M` are the lengths of the subarrays
2function maxSumTwoNoOverlap(nums: number[], L: number, M: number): number {
3    const n: number = nums.length;
4    const prefixSum: number[] = new Array(n + 1).fill(0);
5
6    // Calculate prefix sums
7    for (let i = 0; i < n; ++i) {
8        prefixSum[i + 1] = prefixSum[i] + nums[i];
9    }
10
11    let maxSum: number = 0; // Max sum of two non-overlapping subarrays
12    let maxL: number = 0; // Max sum of subarray with length L
13
14    // First loop: fixing the first subarray with length L and finding optimal M
15    for (let i = L; i + M <= n; ++i) {
16        maxL = Math.max(maxL, prefixSum[i] - prefixSum[i - L]);
17        maxSum = Math.max(maxSum, maxL + prefixSum[i + M] - prefixSum[i]);
18    }
19
20    let maxM: number = 0; // Max sum of subarray with length M
21
22    // Second loop: fixing the first subarray with length M and finding optimal L
23    for (let i = M; i + L <= n; ++i) {
24        maxM = Math.max(maxM, prefixSum[i] - prefixSum[i - M]);
25        maxSum = Math.max(maxSum, maxM + prefixSum[i + L] - prefixSum[i]);
26    }
27
28    // Return the max possible sum of two non-overlapping subarrays
29    return maxSum;
30}
31
Not Sure What to Study? Take the 2-min Quiz：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the nums list. This is because the code iterates over the list twice with while-loops. In each iteration, it performs a constant number of operations (addition, subtraction, and comparison).

The space complexity of the code is O(n), due to the additional list s that is created with the accumulate function to store the prefix sums of the nums list. The size of the s list is directly proportional to the size of the nums list.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫