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 <= 10002 <= firstLen + secondLen <= 1000firstLen + secondLen <= nums.length <= 10000 <= nums[i] <= 1000When 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:
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:
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_sumThe 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:
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| Case | How to Handle |
|---|---|
| Empty input array | Return 0 as there are no subarrays to sum if the input array is empty. |
| Array with a single element | Return 0 as two non-overlapping subarrays cannot be formed. |
| First length equals or exceeds array length | Return 0 as a second non-overlapping subarray of given length cannot be formed |
| Second length equals or exceeds array length | Return 0 as a first non-overlapping subarray of given length cannot be formed |
| Array with all negative numbers | 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 | Use a data type like long to store the sums to prevent integer overflow during calculations. |
| All elements are zero | The sliding window sums will all be zero, so the maximum sum should also be zero. |
| First length + Second Length exceed array length | Return 0 since there is not enough non-overlapping space for both subarrays. |