LeetCode Solutions Blog

Maximum Good Subarray Sum

Number: 3265

Difficulty: Medium

Paid? No

Problem Description

Given an array of integers and a positive integer k, a subarray (of at least two elements) is called good if the absolute difference between its first and last element is exactly k. Return the maximum sum among all such good subarrays. If no good subarray exists, return 0.

Key Insights

The condition |nums[i] - nums[j]| == k (with i < j) translates to two cases: nums[i] == nums[j] + k or nums[i] == nums[j] - k.
A prefix sum array allows O(1) calculation of any subarray sum.
Use a hash table (dictionary) to store the minimum prefix sum for each candidate starting element encountered so far.
For each index j (considered as the end of the subarray), check for a previously seen index i (with i < j) whose value satisfies either condition.
To maximize subarray sum = prefix[j+1] - prefix[i], use the smallest prefix sum corresponding to a valid nums[i].

Space and Time Complexity

Time Complexity: O(n) – We process each element once. Space Complexity: O(n) – In the worst case, the dictionary may store an entry for every distinct element.

Solution

We first compute the prefix sum array where prefix[0] = 0 and prefix[i+1] = prefix[i] + nums[i]. For every new potential ending index j, we require a valid starting index i (i < j) such that |nums[i] - nums[j]| == k. This gives us two possibilities: nums[i] should equal nums[j] - k or nums[j] + k. We maintain a dictionary that maps a number to the minimum prefix sum at an index where that number occurred. When iterating over nums, for every new element (which can serve as the ending element for some subarray), we check if either candidate exists in our dictionary. If so, we calculate the subarray sum as prefix[j+1] minus the stored minimum prefix sum, and update our answer if it is larger. Finally, we update our dictionary with the current element and the prefix sum corresponding to its index if it improves (i.e. is smaller than) the current stored value.

Code Solutions

# Python solution for Maximum Good Subarray Sum

def maximumGoodSubarraySum(nums, k):
    n = len(nums)
    # Compute prefix sum array: prefix[i] is the sum of nums[0...i-1]
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
    
    # Dictionary to map a number to the minimum prefix sum seen so far at the index where that number is encountered.
    best_prefix_for_value = {}
    
    # Initialize with the first element (index 0) to use for future subarrays.
    best_prefix_for_value[nums[0]] = prefix[0]  # prefix[0] is 0
    
    max_sum = None  # Will hold the maximum sum for good subarray
    
    # Iterate over possible end indices starting from 1 since subarray must have at least 2 elements.
    for j in range(1, n):
        current_value = nums[j]
        # Check two candidates:
        # 1. Case: nums[i] = current_value - k
        candidate1 = current_value - k
        if candidate1 in best_prefix_for_value:
            candidate_sum = prefix[j+1] - best_prefix_for_value[candidate1]
            if max_sum is None or candidate_sum > max_sum:
                max_sum = candidate_sum
        
        # 2. Case: nums[i] = current_value + k
        candidate2 = current_value + k
        if candidate2 in best_prefix_for_value:
            candidate_sum = prefix[j+1] - best_prefix_for_value[candidate2]
            if max_sum is None or candidate_sum > max_sum:
                max_sum = candidate_sum
        
        # Update dictionary for the current element.
        # Store the minimum prefix sum for indices that start with this number.
        if current_value in best_prefix_for_value:
            best_prefix_for_value[current_value] = min(best_prefix_for_value[current_value], prefix[j])
        else:
            best_prefix_for_value[current_value] = prefix[j]
    
    # If no good subarray is found, return 0.
    return max_sum if max_sum is not None else 0

# Example usage:
#print(maximumGoodSubarraySum([1,2,3,4,5,6], 1))  # Output: 11
#print(maximumGoodSubarraySum([-1,3,2,4,5], 3))   # Output: 11
#print(maximumGoodSubarraySum([-1,-2,-3,-4], 2))   # Output: -6