# Maximum Good Subarray Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-good-subarray-sum)
Canonical: https://scaleengineer.com/dsa/problems/maximum-good-subarray-sum
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Zepto](https://scaleengineer.com/companies/zepto), [Groww](https://scaleengineer.com/companies/groww)
---
## Problem
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 <= 105`
* `-109 <= nums[i] <= 109`
* `1 <= k <= 109`

# Approaches
## Brute Force with Prefix Sums
This approach iterates through all possible subarrays, checks if they are 'good', and calculates their sum to find the maximum. To optimize sum calculation, it uses a precomputed prefix sum array.
**Time:** O(n^2). The nested loops iterate through all possible start and end points of subarrays, resulting in a quadratic number of pairs to check. The prefix sum calculation takes O(n), but it's dominated by the nested loops. · **Space:** O(n). We need an auxiliary array of size `n+1` to store the prefix sums.
**Pros:** Simple to understand and implement.
**Cons:** Inefficient for large inputs due to its quadratic time complexity, which will likely result in a 'Time Limit Exceeded' error on platforms with large test cases.
### Explanation
The most straightforward way to solve this problem is to examine every possible subarray. A subarray is defined by its start and end indices, `i` and `j`.

We can use nested loops to generate all pairs of `(i, j)` where `i < j`. For each pair, we check if it forms a 'good' subarray by testing the condition `|nums[i] - nums[j]| == k`. If the condition is met, we then need to calculate the sum of the elements in `nums[i..j]`.

A naive sum calculation for each good subarray would involve another loop, leading to an O(n^3) solution. We can optimize this by pre-calculating prefix sums. A prefix sum array, `prefix`, allows us to find the sum of any subarray `nums[i..j]` in O(1) time using the formula `sum = prefix[j+1] - prefix[i]`. This optimization reduces the overall time complexity to O(n^2).

We maintain a variable `maxSum` to keep track of the maximum sum found so far. Since the problem requires returning 0 if no good subarray exists, we use a boolean flag to track whether at least one has been found.

```java
class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        long maxSum = Long.MIN_VALUE;
        boolean found = false;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (Math.abs((long)nums[i] - nums[j]) == k) {
                    found = true;
                    long currentSum = prefix[j + 1] - prefix[i];
                    if (currentSum > maxSum) {
                        maxSum = currentSum;
                    }
                }
            }
        }

        return found ? maxSum : 0;
    }
}
```
### Algorithm
*   Create a prefix sum array `prefix` of size `n+1`, where `prefix[i]` stores the sum of elements from `nums[0]` to `nums[i-1]`.
*   Initialize a variable `maxSum` to a very small value (e.g., `Long.MIN_VALUE`) and a boolean flag `foundGoodSubarray` to `false`.
*   Iterate through the array with a start index `i` from `0` to `n-1`.
*   For each `i`, iterate with an end index `j` from `i+1` to `n-1`.
*   Check if the subarray `nums[i..j]` is good: `if (Math.abs(nums[i] - nums[j]) == k)`.
*   If it's a good subarray, calculate its sum using the prefix sum array: `currentSum = prefix[j+1] - prefix[i]`.
*   Update `maxSum = Math.max(maxSum, currentSum)` and set `foundGoodSubarray` to `true`.
*   After the loops, if `foundGoodSubarray` is `true`, return `maxSum`. Otherwise, return `0`.

## Optimized Single Pass with Hash Map
This approach improves upon the brute-force method by using a hash map to efficiently find the required starting elements for good subarrays. It processes the array in a single pass, achieving linear time complexity.
**Time:** O(n). We iterate through the array once. Hash map operations (get, put) take O(1) on average. The prefix sum calculation also takes O(n). The overall complexity is linear. · **Space:** O(n). We use an O(n) prefix sum array and a hash map that can store up to `n` unique elements in the worst case, leading to O(n) space.
**Pros:** Highly efficient with linear time complexity, making it suitable for large inputs.; This is the optimal solution for the given constraints.
**Cons:** Requires extra space for the hash map and prefix sum array.; Slightly more complex to reason about than the brute-force approach.
### Explanation
To optimize the search for the maximum good subarray sum, we can rephrase the problem. For each possible endpoint `j` of a subarray, we want to find the best possible starting point `i < j` that satisfies `|nums[i] - nums[j]| == k` and maximizes the sum `sum(nums[i..j])`.

Using prefix sums, the sum is `prefix[j+1] - prefix[i]`. For a fixed `j`, maximizing this sum is equivalent to minimizing `prefix[i]`.

The condition `|nums[i] - nums[j]| == k` means we are looking for a starting element `nums[i]` that is equal to either `nums[j] - k` or `nums[j] + k`.

This leads to an efficient O(n) algorithm. We iterate through the array from left to right (index `j` from `0` to `n-1`). We use a hash map to store the minimum prefix sum encountered so far for each number value. Let this map be `minPrefixSumMap`, where `map.get(v)` gives the minimum `prefix[i]` for all `i` processed so far where `nums[i] == v`.

In each iteration `j`:
1.  **Find a good subarray:** We check if the map contains keys for `nums[j] - k` or `nums[j] + k`. If it does, we have found a potential starting point `i < j`. We calculate the sum using the stored minimum prefix sum (`prefix[j+1] - minPrefixSumMap.get(target)`) and update our `maxSum`.
2.  **Update the map:** We then update the map with the information from the current index `j`. We record `prefix[j]` as a possible minimum prefix sum for the value `nums[j]`. This makes `nums[j]` available as a starting point for subsequent elements.

The order of these two steps is crucial. By checking for a subarray *before* updating the map, we ensure that we only consider starting indices `i` that are strictly less than the current ending index `j`.

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

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        long maxSum = Long.MIN_VALUE;
        boolean found = false;
        Map<Integer, Long> minPrefixSumMap = new HashMap<>();

        for (int j = 0; j < n; j++) {
            int val = nums[j];
            
            // 1. Check for good subarrays ending at j
            int target1 = val - k;
            if (minPrefixSumMap.containsKey(target1)) {
                long currentSum = prefix[j + 1] - minPrefixSumMap.get(target1);
                maxSum = Math.max(maxSum, currentSum);
                found = true;
            }

            int target2 = val + k;
            if (minPrefixSumMap.containsKey(target2)) {
                long currentSum = prefix[j + 1] - minPrefixSumMap.get(target2);
                maxSum = Math.max(maxSum, currentSum);
                found = true;
            }

            // 2. Update map with info from index j
            long currentPrefix = prefix[j];
            if (!minPrefixSumMap.containsKey(val) || currentPrefix < minPrefixSumMap.get(val)) {
                minPrefixSumMap.put(val, currentPrefix);
            }
        }

        return found ? maxSum : 0;
    }
}
```
### Algorithm
*   Compute a prefix sum array `prefix` of size `n+1`.
*   Initialize `maxSum = Long.MIN_VALUE`, a boolean `foundGoodSubarray = false`, and a hash map `minPrefixSumMap` to store `(value, min_prefix_sum)` pairs.
*   Iterate through the array with index `j` from `0` to `n-1`.
*   For the current element `nums[j]`, consider it as the end of a subarray. Look for a valid start `i < j`.
*   Check for the two possible starting values: `target1 = nums[j] - k` and `target2 = nums[j] + k`.
*   If `minPrefixSumMap` contains `target1`, calculate the sum `currentSum = prefix[j+1] - minPrefixSumMap.get(target1)` and update `maxSum` and `foundGoodSubarray`.
*   If `minPrefixSumMap` contains `target2`, do the same.
*   After checking, update the map for `nums[j]` to be a potential start for future subarrays. Store `prefix[j]` for the key `nums[j]`, keeping the minimum if the key already exists: `map.put(nums[j], Math.min(map.getOrDefault(nums[j], Long.MAX_VALUE), prefix[j]))`.
*   After the loop, if a good subarray was found, return `maxSum`. Otherwise, return `0`.

# Solutions
### CSharp

```csharp
public class Solution {
    public long MaximumSubarraySum(int[] nums, int k) {
        Dictionary < int, long > p = new Dictionary < int, long > ();
        p[nums[0]] = 0 L;
        long s = 0;
        int n = nums.Length;
        long ans = long.MinValue;
        for (int i = 0; i < n; ++i) {
            s += nums[i];
            if (p.ContainsKey(nums[i] - k)) {
                ans = Math.Max(ans, s - p[nums[i] - k]);
            }
            if (p.ContainsKey(nums[i] + k)) {
                ans = Math.Max(ans, s - p[nums[i] + k]);
            }
            if (i + 1 < n && (!p.ContainsKey(nums[i + 1]) || p[nums[i + 1]] > s)) {
                p[nums[i + 1]] = s;
            }
        }
        return ans == long.MinValue ? 0 : ans;
    }
}
```

### Java

```java
class Solution {
public
  long maximumSubarraySum(int[] nums, int k) {
    Map<Integer, Long> p = new HashMap<>();
    p.put(nums[0], 0L);
    long s = 0;
    int n = nums.length;
    long ans = Long.MIN_VALUE;
    for (int i = 0; i < n; ++i) {
      s += nums[i];
      if (p.containsKey(nums[i] - k)) {
        ans = Math.max(ans, s - p.get(nums[i] - k));
      }
      if (p.containsKey(nums[i] + k)) {
        ans = Math.max(ans, s - p.get(nums[i] + k));
      }
      if (i + 1 < n &&
          (!p.containsKey(nums[i + 1]) || p.get(nums[i + 1]) > s)) {
        p.put(nums[i + 1], s);
      }
    }
    return ans == Long.MIN_VALUE ? 0 : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maximumSubarraySum(vector<int> &nums, int k) {
    unordered_map<int, long long> p;
    p[nums[0]] = 0;
    long long s = 0;
    const int n = nums.size();
    long long ans = LONG_LONG_MIN;
    for (int i = 0;; ++i) {
      s += nums[i];
      auto it = p.find(nums[i] - k);
      if (it != p.end()) {
        ans = max(ans, s - it->second);
      }
      it = p.find(nums[i] + k);
      if (it != p.end()) {
        ans = max(ans, s - it->second);
      }
      if (i + 1 == n) {
        break;
      }
      it = p.find(nums[i + 1]);
      if (it == p.end() || it->second > s) {
        p[nums[i + 1]] = s;
      }
    }
    return ans == LONG_LONG_MIN ? 0 : ans;
  }
};

```

### Python

```python
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int: ans = - inf p = {nums[0]: 0} s, n = 0, len(nums) for i, x in enumerate(nums): s += x if x - k in p: ans = max(ans, s - p[x - k]) if x + k in p: ans = max(ans, s - p[x + k]) if i + 1 < n and (nums[i + 1] not in p or p[nums[i + 1]] > s): p[nums[i + 1]] = s return 0 if ans == - inf else ans

```