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 _themaximum sum of a good subarray of _nums. If there are no good subarrays , return0.

Examples

Example 1

1
2
3

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

1
2
3

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

1
2
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
  • -109 <= nums[i] <= 10^9
  • 1 <= k <= 10^9

Solution

Method 1 – Prefix Sum with Hash Map

Intuition

We want to find the maximum sum of a subarray whose first and last elements differ by exactly k. For each index, we can use prefix sums and a hash map to track the best prefix sum for each possible value of nums[i] ± k. This allows us to efficiently check for all possible good subarrays ending at each index.

Approach

  1. Initialize a hash map to store the maximum prefix sum for each value seen so far.
  2. Compute prefix sums as we iterate through the array.
  3. For each index i:
    • If nums[i] + k exists in the map, update the answer with the sum of the subarray from the previous occurrence to i.
    • If nums[i] - k exists in the map, update the answer similarly.
    • Update the map for nums[i] with the maximum prefix sum ending at i.
  4. Return the maximum sum found, or 0 if no good subarray exists.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, long long> mp;
        long long ans = LLONG_MIN, sum = 0;
        mp[nums[0]] = 0;
        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i];
            if (mp.count(nums[i] + k)) ans = max(ans, sum - mp[nums[i] + k]);
            if (mp.count(nums[i] - k)) ans = max(ans, sum - mp[nums[i] - k]);
            if (!mp.count(nums[i])) mp[nums[i]] = sum;
        }
        return ans == LLONG_MIN ? 0 : ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func maximumSubarraySum(nums []int, k int) int64 {
    mp := map[int]int64{}
    var ans int64 = -1 << 63
    var sum int64 = 0
    mp[nums[0]] = 0
    for i := 0; i < len(nums); i++ {
        sum += int64(nums[i])
        if v, ok := mp[nums[i]+k]; ok {
            if sum-v > ans {
                ans = sum - v
            }
        }
        if v, ok := mp[nums[i]-k]; ok {
            if sum-v > ans {
                ans = sum - v
            }
        }
        if _, ok := mp[nums[i]]; !ok {
            mp[nums[i]] = sum
        }
    }
    if ans == -1<<63 {
        return 0
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        Map<Integer, Long> mp = new HashMap<>();
        long ans = Long.MIN_VALUE, sum = 0;
        mp.put(nums[0], 0L);
        for (int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            if (mp.containsKey(nums[i] + k)) ans = Math.max(ans, sum - mp.get(nums[i] + k));
            if (mp.containsKey(nums[i] - k)) ans = Math.max(ans, sum - mp.get(nums[i] - k));
            mp.putIfAbsent(nums[i], sum);
        }
        return ans == Long.MIN_VALUE ? 0 : ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun maximumSubarraySum(nums: IntArray, k: Int): Long {
        val mp = mutableMapOf<Int, Long>()
        var ans = Long.MIN_VALUE
        var sum = 0L
        mp[nums[0]] = 0L
        for (i in nums.indices) {
            sum += nums[i]
            mp[nums[i]+k]?.let { ans = maxOf(ans, sum - it) }
            mp[nums[i]-k]?.let { ans = maxOf(ans, sum - it) }
            mp.putIfAbsent(nums[i], sum)
        }
        return if (ans == Long.MIN_VALUE) 0L else ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def maximumSubarraySum(self, nums: list[int], k: int) -> int:
        mp: dict[int, int] = {nums[0]: 0}
        ans = float('-inf')
        s = 0
        for x in nums:
            s += x
            if x + k in mp:
                ans = max(ans, s - mp[x + k])
            if x - k in mp:
                ans = max(ans, s - mp[x - k])
            if x not in mp:
                mp[x] = s
        return 0 if ans == float('-inf') else ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn maximum_subarray_sum(nums: Vec<i32>, k: i32) -> i64 {
        use std::collections::HashMap;
        let mut mp = HashMap::new();
        let mut ans = i64::MIN;
        let mut sum = 0i64;
        mp.insert(nums[0], 0i64);
        for &x in &nums {
            sum += x as i64;
            if let Some(&v) = mp.get(&(x + k)) {
                ans = ans.max(sum - v);
            }
            if let Some(&v) = mp.get(&(x - k)) {
                ans = ans.max(sum - v);
            }
            mp.entry(x).or_insert(sum);
        }
        if ans == i64::MIN { 0 } else { ans }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    maximumSubarraySum(nums: number[], k: number): number {
        const mp: Record<number, number> = {[nums[0]]: 0};
        let ans = -Infinity, sum = 0;
        for (const x of nums) {
            sum += x;
            if (mp[x + k] !== undefined) ans = Math.max(ans, sum - mp[x + k]);
            if (mp[x - k] !== undefined) ans = Math.max(ans, sum - mp[x - k]);
            if (mp[x] === undefined) mp[x] = sum;
        }
        return ans === -Infinity ? 0 : ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), since we process each element once and hash map operations are O(1) on average.
  • 🧺 Space complexity: O(n), for the hash map storing prefix sums for each unique value.