Maximum Good Subarray Sum

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^9
• 1 <= k <= 10^9

## Maximum Sum of Good Subarray

This problem asks us to find the maximum sum of a "good" subarray within a given array `nums`. A subarray is considered "good" if the absolute difference between its first and last element is exactly `k`. If no such subarray exists, we should return 0.

### 1. Brute Force Solution

The most straightforward approach is to iterate through all possible subarrays, check if each subarray is "good", and keep track of the maximum sum among the good subarrays.  This involves nested loops to define the start and end indices of each subarray.

```python
def max_sum_good_subarray_brute_force(nums, k):
    n = len(nums)
    max_sum = 0

    for i in range(n):
        for j in range(i, n):
            subarray = nums[i:j+1]
            if abs(subarray[0] - subarray[-1]) == k:
                max_sum = max(max_sum, sum(subarray))

    return max_sum

Example:

nums = [1, 2, 3, 4, 5, 6]
k = 1
print(max_sum_good_subarray_brute_force(nums, k))  # Output: 11

2. Optimal Solution

Instead of recalculating the sum of each subarray, we can keep a running sum. This improves the time complexity.

def max_sum_good_subarray_optimal(nums, k):
    n = len(nums)
    max_sum = 0

    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += nums[j]
            if abs(nums[i] - nums[j]) == k:
                max_sum = max(max_sum, current_sum)

    return max_sum

Explanation:

• We iterate through all possible starting indices i.
• For each starting index, we iterate through all possible ending indices j from i to the end of the array.
• We maintain a current_sum that represents the sum of the current subarray from i to j.
• If the absolute difference between nums[i] and nums[j] is equal to k, we update max_sum with the maximum of max_sum and current_sum.

3. Time Complexity Analysis

• Brute Force: The nested loops iterate through all possible subarrays, which results in O(n^2) subarrays. For each subarray, we calculate the sum, which takes O(n) time in the worst case (although summing can be done in O(1) with prefix sums). Thus, overall time complexity is O(n^2).
• Optimal Solution: The nested loops still iterate through all possible subarrays in O(n^2) time. However, checking the absolute difference and updating the sum are O(1) operations. Hence, the overall time complexity is O(n^2).

4. Space Complexity Analysis

• Brute Force: O(1), excluding the space for the input array. The extra space used is constant.
• Optimal Solution: O(1), excluding the space for the input array. We only use a few extra variables (e.g., max_sum, current_sum, i, j), so the space complexity is constant.

5. Edge Cases

1. Empty Array: If the input array is empty, the function should return 0.
2. No Good Subarrays: If no subarray satisfies the condition |nums[i] - nums[j]| == k, the function should return 0.
3. Negative Numbers: The array can contain negative numbers, so the sum can be negative. The algorithm should correctly handle this.
4. k = 0: If k is zero, we only consider subarrays where the first and last elements are the same.
5. Large Input Size: While the provided code will work for reasonably large input sizes within the constraints, further optimizations (e.g. using a hash map if the problem allowed for a different definition of "good" subarray) might be required for significantly larger datasets to reduce runtime if the problem's constraints changed.