Maximum Good Subarray Sum
Medium
You are given an array nums of length n and a positive integer k. A subarray of nums is called good if the absolute difference between its first and last element is exactly k, in other words, the subarray nums[i..j] is good if |nums[i] - nums[j]| == k. Return the maximum sum of a good subarray of nums. If there are no good subarrays, return 0.
Example 1:
Input: nums = [1,2,3,4,5,6], k = 1
Output: 11
Explanation: The absolute difference between the first and last element must be 1 for a good subarray. All the good subarrays are: [1,2], [2,3], [3,4], [4,5], and [5,6]. The maximum subarray sum is 11 for the subarray [5,6].
Example 2:
Input: nums = [-1,3,2,4,5], k = 3
Output: 11
Explanation: The absolute difference between the first and last element must be 3 for a good subarray. All the good subarrays are: [-1,3,2], and [2,4,5]. The maximum subarray sum is 11 for the subarray [2,4,5].
Example 3:
Input: nums = [-1,-2,-3,-4], k = 2
Output: -6
Explanation: The absolute difference between the first and last element must be 2 for a good subarray. All the good subarrays are: [-1,-2,-3], and [-2,-3,-4]. The maximum subarray sum is -6 for the subarray [-1,-2,-3].
Constraints:
2 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^91 <= k <= 10^9
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:
- What is the range of integer values within the input array?
- Can the input array be empty or null?
- If no subarray has a positive sum, what should I return (e.g., 0, null, an empty array)?
- By 'subarray', do you mean a contiguous subarray?
- Is there a specific criterion for choosing the 'best' subarray if multiple subarrays have the same maximum sum (e.g., shortest length, earliest starting index)?
Brute Force Solution
Approach
The brute force approach to finding the maximum good subarray sum involves checking every possible subarray within the given input. We calculate the sum of each of these subarrays and determine if it is a 'good' subarray, according to the problem's specific criteria. Finally, we compare all of the sums from the 'good' subarrays and select the largest one.
Here's how the algorithm would work step-by-step:
- Start with the very first number in the list.
- Consider only that number as a subarray and calculate its sum.
- Then, consider the first two numbers as a subarray and calculate their sum.
- Next, consider the first three numbers, and so on, each time calculating the sum of the growing subarray.
- Continue this process until you have considered the entire list as the initial subarray.
- Now, start again, but begin with the second number in the list.
- Repeat the process of creating progressively larger subarrays, calculating their sums, until you reach the end of the list.
- Keep doing this, each time starting from the next number in the list, until you've started from every number.
- For each subarray you considered, check if it is a 'good' subarray, based on some predefined set of rules.
- If a subarray is 'good', store its sum.
- Once you have examined all possible subarrays, compare the sums of all the 'good' subarrays.
- The largest of these sums is the answer.
Code Implementation
def maximum_good_subarray_sum_brute_force(numbers): maximum_sum = float('-inf')
list_length = len(numbers)
for start_index in range(list_length):
for end_index in range(start_index, list_length):
current_subarray = numbers[start_index:end_index + 1]
current_sum = sum(current_subarray)
# Check if the current subarray is considered 'good'
if is_good_subarray(current_subarray):
# Update maximum_sum if current_sum is larger
maximum_sum = max(maximum_sum, current_sum)
return maximum_sum
def is_good_subarray(subarray):
if not subarray:
return False
# Placeholder function for defining what a 'good' subarray is
# Replace with your actual 'good' subarray logic
for number in subarray:
if number < 0:
return False
return TrueBig(O) Analysis
Optimal Solution
Approach
The key idea is to keep track of the best possible sum ending at each point in the list. As we go, if the running sum ever dips below zero, we simply restart from zero. This avoids dragging down future sums with negative baggage.
Here's how the algorithm would work step-by-step:
- Start at the beginning of the list and keep a running total of the numbers we've seen so far.
- If the running total ever becomes negative, reset it to zero. This is because a negative running total will always decrease any future subarray sum.
- As we go, remember the largest running total we've encountered. This is the maximum good subarray sum.
- Continue to the end of the list, updating the running total and the maximum sum as necessary.
- Once we've reached the end, the largest running total we saved is the answer.
Code Implementation
def max_good_subarray_sum(numbers):
maximum_sum_so_far = 0
current_sum = 0
for number in numbers:
current_sum += number
# Reset current sum to 0 if it becomes negative.
if current_sum < 0:
current_sum = 0
# Update the maximum sum found so far.
if current_sum > maximum_sum_so_far:
maximum_sum_so_far = current_sum
return maximum_sum_so_farBig(O) Analysis
Edge Cases
| Case | How to Handle |
|---|---|
| Empty input array | Return 0, as there's no subarray to sum. |
| Array with a single element | Return the single element if it's positive; otherwise, return 0. |
| Array with all negative numbers | Return 0, as an empty subarray is better than any negative sum. |
| Array with all zeros | Return 0, the sum of the entire array. |
| Array with very large positive numbers causing potential integer overflow | Use a data type with a larger range, like long, to store intermediate sums. |
| Array with alternating large positive and large negative numbers | Kadane's Algorithm correctly handles fluctuations, maximizing good subarrays. |
| Maximum-sized array (constrained by memory) | Kadane's Algorithm runs in O(n) time and O(1) space, making it efficient even for large arrays. |
| All numbers are the same positive value | The algorithm correctly sums the entire array to provide the maximum sum. |
