Pseudo-code:

text
max_sum = negative_infinity
found_valid = false

for i from 0 to n-1:
    current_subarray_sum = 0
    for j from i to n-1:
        current_subarray_sum += nums[j]
        if abs(nums[i] - nums[j]) == k:
            max_sum = max(max_sum, current_subarray_sum)
            found_valid = true

return found_valid ? max_sum : 0

Why this fails: The time complexity of this approach is $O(N^2)$. Given the constraint nums.length <= 10^5, an $O(N^2)$ solution requires approximately $10^{10}$ operations, which far exceeds the typical limit of $10^8$ operations per second allowed by LeetCode. This will result in a Time Limit Exceeded (TLE) error.

Core Insight for Maximum Good Subarray Sum

To optimize the brute force approach, we must avoid recalculating sums repeatedly and avoid searching for the left boundary i linearly.

The sum of a subarray nums[i..j] can be expressed using prefix sums: $\text{Sum}(i, j) = \text{PrefixSum}[j] - \text{PrefixSum}[i-1]$

We iterate j from $0$ to $n-1$. For the current element nums[j], we need to find a previous index i such that: $|nums[i] - nums[j]| = k$ This implies nums[i] must be either nums[j] - k or nums[j] + k.

To maximize the total subarray sum, we need to minimize PrefixSum[i-1].

Instead of scanning backwards for i, we can use a Hash Map to store the minimal prefix sum encountered before every unique value x seen so far. As we slide the right boundary j forward, we perform an $O(1)$ lookup in our map to see if a valid nums[i] exists and immediately calculate the potential max sum.

Visual Description: Imagine traversing the array. At each step, you calculate the cumulative sum. You record this cumulative sum in a dictionary keyed by the current number value. If you encounter the number 5, and the cumulative sum just before this 5 was 10, you store {5: 10}. Later, if you encounter a number that needs a 5 to complete the "good" condition, you look up 5 in your dictionary. If the dictionary returns 10, you know that a subarray starting with 5 would subtract 10 from your current total cumulative sum. By storing only the minimum previous cumulative sum for each number, you ensure that any "window" you form is maximal.

Execution Flow

1. Initialize max_sum to a very small number (e.g., negative infinity) to handle negative sums.
2. Initialize current_sum to 0.
3. Initialize min_prefix_map as an empty hash map.
4. Iterate through nums with index j and value num:
   • Add num to current_sum.
   • Check Condition:
     • If num - k exists in min_prefix_map:
       • candidate = current_sum - min_prefix_map[num - k]
       • max_sum = max(max_sum, candidate)
     • If num + k exists in min_prefix_map:
       • candidate = current_sum - min_prefix_map[num + k]
       • max_sum = max(max_sum, candidate)
   • Update Map:
     • The prefix sum before adding num is current_sum - num.
     • If num is not in min_prefix_map OR (current_sum - num) < min_prefix_map[num]:
       • Set min_prefix_map[num] = current_sum - num.
5. If max_sum is still negative infinity (no good subarray found), return 0. Otherwise, return max_sum.

Proof of Correctness

The algorithm relies on the arithmetic property of contiguous subarray sums: $\text{Sum}(i, j) = P_j - P_{i-1}$. For a fixed ending position $j$, the sum is maximized when $P_{i-1}$ is minimized. Our map invariant ensures that min_prefix_map[val] always holds the minimum $P_{i-1}$ for any index $i$ seen so far where nums[i] == val. Therefore, when we check for nums[j] - k or nums[j] + k, we are guaranteed to calculate the maximum possible sum for a good subarray ending at $j$. Since we iterate through all possible end positions $j$, the global maximum is guaranteed to be found.

Reference Implementation

C++ Solution for LeetCode 3026

cpp
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        // Use a large negative number as sentinel. 
        // 0 is not safe because valid sums can be negative.
        long long max_sum = LLONG_MIN;
        
        // Map stores: value -> minimum prefix sum strictly before that value
        unordered_map<int, long long> min_prefix;
        
        long long current_sum = 0;
        
        for (int num : nums) {
            // Update running sum (PrefixSum[j])
            current_sum += num;
            
            // Check for target: num - k
            if (min_prefix.count(num - k)) {
                long long current_good_sum = current_sum - min_prefix[num - k];
                if (current_good_sum > max_sum) {
                    max_sum = current_good_sum;
                }
            }
            
            // Check for target: num + k
            if (min_prefix.count(num + k)) {
                long long current_good_sum = current_sum - min_prefix[num + k];
                if (current_good_sum > max_sum) {
                    max_sum = current_good_sum;
                }
            }
            
            // Update map with current number.
            // We store the prefix sum BEFORE adding the current number.
            long long prefix_before_current = current_sum - num;
            
            if (!min_prefix.count(num) || prefix_before_current < min_prefix[num]) {
                min_prefix[num] = prefix_before_current;
            }
        }
        
        // If max_sum was never updated, no good subarray exists.
        return (max_sum == LLONG_MIN) ? 0 : max_sum;
    }
};

Java Solution for LeetCode 3026

java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        // Use Long.MIN_VALUE as sentinel
        long maxSum = Long.MIN_VALUE;
        
        // Map stores: value -> minimum prefix sum strictly before that value
        Map<Integer, Long> minPrefix = new HashMap<>();
        
        long currentSum = 0;
        
        for (int num : nums) {
            currentSum += num;
            
            // Check for targets
            if (minPrefix.containsKey(num - k)) {
                maxSum = Math.max(maxSum, currentSum - minPrefix.get(num - k));
            }
            
            if (minPrefix.containsKey(num + k)) {
                maxSum = Math.max(maxSum, currentSum - minPrefix.get(num + k));
            }
            
            // Update map logic
            long prefixBeforeCurrent = currentSum - num;
            
            if (!minPrefix.containsKey(num) || prefixBeforeCurrent < minPrefix.get(num)) {
                minPrefix.put(num, prefixBeforeCurrent);
            }
        }
        
        return maxSum == Long.MIN_VALUE ? 0 : maxSum;
    }
}

Python Solution for LeetCode 3026

python
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        # Initialize with infinity to handle negative max sums correctly
        max_sum = float('-inf')
        
        # Map stores: value -> minimum prefix sum strictly before that value
        min_prefix = {}
        
        current_sum = 0
        
        for num in nums:
            current_sum += num
            
            # Check if valid start points exist in map
            if (num - k) in min_prefix:
                max_sum = max(max_sum, current_sum - min_prefix[num - k])
            
            if (num + k) in min_prefix:
                max_sum = max(max_sum, current_sum - min_prefix[num + k])
            
            # The prefix sum before adding the current number
            prefix_before_current = current_sum - num
            
            # Only update map if we found a smaller prefix sum for this value
            if num not in min_prefix or prefix_before_current < min_prefix[num]:
                min_prefix[num] = prefix_before_current
                
        return 0 if max_sum == float('-inf') else max_sum