Taro Logo

Maximum Sum of Two Non-Overlapping Subarrays

Medium
Asked by:
Profile picture
64 views
Topics:
ArraysSliding WindowsDynamic Programming

Given an integer array nums and two integers firstLen and secondLen, return the maximum sum of elements in two non-overlapping subarrays with lengths firstLen and secondLen.

The array with length firstLen could occur before or after the array with length secondLen, but they have to be non-overlapping.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20
Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.

Example 2:

Input: nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
Output: 29
Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.

Example 3:

Input: nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
Output: 31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [0,3,8] with length 3.

Constraints:

  • 1 <= firstLen, secondLen <= 1000
  • 2 <= firstLen + secondLen <= 1000
  • firstLen + secondLen <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the possible ranges for the values in the input array, and can the array contain negative numbers or zeros?
  2. If no two non-overlapping subarrays of the specified lengths exist, what should I return?
  3. Are the lengths of the subarrays (firstLen and secondLen) always positive integers?
  4. If multiple pairs of non-overlapping subarrays yield the same maximum sum, is any one of them acceptable, or is there a specific pair I should aim to return?
  5. Can firstLen and secondLen be equal, and are they always less than or equal to the length of the input array?

Brute Force Solution

Approach

The brute force approach finds the best possible result by simply looking at every single option, even if it takes a long time. It's like trying every combination until you find the one that works the best. For this problem, we will consider every possible way to split the input into two parts and then look at every possible subpart of each part.

Here's how the algorithm would work step-by-step:

  1. First, imagine dividing the entire input into two separate pieces in every possible way. Think of it like drawing a line at different spots to split a long string into two shorter strings.
  2. For the first piece, consider every possible smaller chunk within it. Find the sum of all these chunks and keep track of the largest sum you see.
  3. Do the same thing for the second piece. That is, consider every possible chunk of the second piece, find their sums, and remember the largest sum.
  4. Now, add the largest sum from the first piece and the largest sum from the second piece together. This gives you a total sum for that particular splitting of the original input.
  5. Repeat all the previous steps for every single way you can split the original input into two pieces.
  6. Finally, compare all the total sums you calculated in the previous steps. Choose the largest total sum from all the different splits and their respective best chunks. This is the answer.

Code Implementation

def maximum_sum_two_non_overlapping_subarrays_brute_force(input_array):
    maximum_sum = 0

    # Iterate through all possible split points
    for split_point in range(1, len(input_array)): 

        # First subarray: from start to split_point
        first_subarray = input_array[:split_point]
        maximum_first_subarray_sum = 0

        # Find the maximum sum of all subarrays within the first subarray
        for first_subarray_start_index in range(len(first_subarray)): 
            for first_subarray_end_index in range(first_subarray_start_index, len(first_subarray)): 
                current_first_subarray_sum = sum(first_subarray[first_subarray_start_index:first_subarray_end_index+1])
                maximum_first_subarray_sum = max(maximum_first_subarray_sum, current_first_subarray_sum)

        # Second subarray: from split_point to end
        second_subarray = input_array[split_point:]
        maximum_second_subarray_sum = 0

        # Find the maximum sum of all subarrays within the second subarray
        for second_subarray_start_index in range(len(second_subarray)): 
            for second_subarray_end_index in range(second_subarray_start_index, len(second_subarray)): 
                current_second_subarray_sum = sum(second_subarray[second_subarray_start_index:second_subarray_end_index+1])
                maximum_second_subarray_sum = max(maximum_second_subarray_sum, current_second_subarray_sum)

        # Update the overall maximum sum
        maximum_sum = max(maximum_sum, maximum_first_subarray_sum + maximum_second_subarray_sum)

    return maximum_sum

Big(O) Analysis

Time Complexity
O(n^3) – The brute force approach first iterates through all possible splitting points of the input array of size n, which takes O(n) time. For each split, it calculates the maximum subarray sum for the left subarray. This requires iterating through all possible subarrays, taking O(n^2) time. Similarly, it calculates the maximum subarray sum for the right subarray, also taking O(n^2) time. Therefore, the overall time complexity is O(n * (n^2 + n^2)) which simplifies to O(n^3).
Space Complexity
O(1) – The provided brute force approach primarily uses a few variables to store intermediate sums and the maximum sum found so far. It does not create any auxiliary data structures like arrays, lists, or hash maps that scale with the input size N (where N is the length of the input array). Therefore, the extra space used remains constant regardless of the input size, resulting in a space complexity of O(1).

Optimal Solution

Approach

The key to efficiently finding the maximum sum lies in pre-calculating sums to avoid redundant calculations. We figure out the best sums for subarrays ending at each position from both the left and the right, then combine the best ones to find the overall maximum.

Here's how the algorithm would work step-by-step:

  1. Calculate the sums of all possible subarrays of the first required size that begin at each possible starting point from the left of the given sequence.
  2. Find the largest sum among these subarrays ending at each position from the left of the given sequence.
  3. Calculate the sums of all possible subarrays of the second required size that begin at each possible starting point from the right of the given sequence.
  4. Find the largest sum among these subarrays ending at each position from the right of the given sequence.
  5. Combine the largest sums obtained from both sides in a way that ensures the subarrays do not overlap. Compare the sums of the largest subarrays found on the left and right, positioning them at every valid combination in the original sequence to ensure they do not overlap.
  6. Keep track of the largest combined sum found so far.
  7. After checking all valid non-overlapping subarray combinations, report the largest combined sum, which represents the maximum possible sum of two non-overlapping subarrays of the given sizes.

Code Implementation

def find_max_sum_two_non_overlapping_subarrays(given_array, first_subarray_length, second_subarray_length):
    array_length = len(given_array)
    max_sum = 0

    # Store max subarray sums ending at each index, starting from the left
    left_max_sums = [0] * array_length
    current_sum = sum(given_array[:first_subarray_length])
    left_max_sums[first_subarray_length - 1] = current_sum
    max_so_far = current_sum
    for i in range(first_subarray_length, array_length):
        current_sum += given_array[i] - given_array[i - first_subarray_length]
        max_so_far = max(max_so_far, current_sum)
        left_max_sums[i] = max_so_far

    # Store max subarray sums ending at each index, starting from the right
    right_max_sums = [0] * array_length
    current_sum = sum(given_array[array_length - second_subarray_length:])
    right_max_sums[array_length - second_subarray_length] = current_sum
    max_so_far = current_sum
    for i in range(array_length - second_subarray_length - 1, -1, -1):
        current_sum += given_array[i] - given_array[i + second_subarray_length]
        max_so_far = max(max_so_far, current_sum)
        right_max_sums[i] = max_so_far

    # Iterate through all possible split points to find the max sum
    for i in range(first_subarray_length - 1, array_length - second_subarray_length):
        max_sum = max(max_sum, left_max_sums[i] + right_max_sums[i + 1])

    # Repeat the same process, swapping subarray lengths
    left_max_sums = [0] * array_length
    current_sum = sum(given_array[:second_subarray_length])
    left_max_sums[second_subarray_length - 1] = current_sum
    max_so_far = current_sum

    # Precompute sums ending at each index from the left.
    for i in range(second_subarray_length, array_length):
        current_sum += given_array[i] - given_array[i - second_subarray_length]
        max_so_far = max(max_so_far, current_sum)
        left_max_sums[i] = max_so_far

    right_max_sums = [0] * array_length
    current_sum = sum(given_array[array_length - first_subarray_length:])
    right_max_sums[array_length - first_subarray_length] = current_sum
    max_so_far = current_sum

    # Precompute sums ending at each index from the right.
    for i in range(array_length - first_subarray_length - 1, -1, -1):
        current_sum += given_array[i] - given_array[i + first_subarray_length]
        max_so_far = max(max_so_far, current_sum)
        right_max_sums[i] = max_so_far

    # Combine the left and right max sums with swapped lengths
    for i in range(second_subarray_length - 1, array_length - first_subarray_length):
        max_sum = max(max_sum, left_max_sums[i] + right_max_sums[i + 1])

    # Ensure to return the overall maximum sum.
    return max_sum

Big(O) Analysis

Time Complexity
O(n) – The algorithm calculates the sums of all subarrays of the first size from the left, which takes O(n) time. Similarly, calculating the sums of all subarrays of the second size from the right also takes O(n) time. Finding the maximum sum subarrays from both left and right involve single iterations that also take O(n). Combining these maximum sums while ensuring non-overlap requires iterating through the array once more, leading to an O(n) operation. Therefore, the overall time complexity is dominated by these linear operations, resulting in O(n).
Space Complexity
O(N) – The algorithm calculates and stores the largest sum of subarrays ending at each position from both the left and the right of the sequence. This requires creating two auxiliary arrays, one to store the maximum subarray sums from the left and another to store the maximum subarray sums from the right. Each of these arrays has a size equal to N, where N is the length of the input sequence. Therefore, the space complexity is O(N).

Edge Cases

Empty input array
How to Handle:
Return 0 as there are no subarrays to sum if the input array is empty.
Array with a single element
How to Handle:
Return 0 as two non-overlapping subarrays cannot be formed.
First length equals or exceeds array length
How to Handle:
Return 0 as a second non-overlapping subarray of given length cannot be formed
Second length equals or exceeds array length
How to Handle:
Return 0 as a first non-overlapping subarray of given length cannot be formed
Array with all negative numbers
How to Handle:
The sliding window will handle negative sums, returning the least negative (closest to zero) sum, which could be the best solution in this scenario.
Array with large positive and negative numbers leading to potential integer overflow
How to Handle:
Use a data type like long to store the sums to prevent integer overflow during calculations.
All elements are zero
How to Handle:
The sliding window sums will all be zero, so the maximum sum should also be zero.
First length + Second Length exceed array length
How to Handle:
Return 0 since there is not enough non-overlapping space for both subarrays.