3026. Maximum Good Subarray Sum - Detailed Explanation

Problem Statement

You’re given an integer array nums of length n and a positive integer k.
A subarray nums[i..j] is good if

|nums[i] – nums[j]| == k

Return the maximum sum of any good subarray. If there is no good subarray, return 0.

Example 1

Input:  nums = [1,2,3,4,5,6], k = 1
Output: 11
Explanation: Good subarrays are [1,2],[2,3],[3,4],[4,5],[5,6]. The largest sum is 5+6 = 11.

Example 2

Input:  nums = [-1,3,2,4,5], k = 3
Output: 11
Explanation: Good subarrays are [-1,3,2] (sum=4) and [2,4,5] (sum=11). Answer = 11.

Example 3

Input:  nums = [-1,-2,-3,-4], k = 2
Output: -6
Explanation: Good subarrays are [-1,-2,-3] (sum=-6) and [-2,-3,-4] (sum=-9). Answer = -6.

Constraints

• 2 ≤ n = nums.length ≤ 10⁵
• –10⁹ ≤ nums[i] ≤ 10⁹
• 1 ≤ k ≤ 10⁹

Brute Force Approach

Try every subarray (i,j) in O(n²):

1. Compute prefix sums S, where S[t] = sum of nums[0..t-1].
2. For each 0 ≤ i < j < n, if |nums[i]–nums[j]|==k, consider sum = S[j+1]–S[i] and track the max.

Time O(n²), Space O(n). Fails for n up to 10⁵.

Optimal Approach: Prefix Sum + Hash Map

Maintain a running sum s_i = sum(nums[0..i]) and a map firstOccur from value → smallest prefix sum before that value’s index.

• Initialize firstOccur = {} and ans = –∞.
• Let s = 0.
• Iterate i from 0 to n–1 with x = nums[i]:
  1. Let prev = s, then s += x (so s = s_i).
  2. For each target end difference v ∈ {x–k, x+k}:
     • If v in firstOccur, a good subarray nums[j..i] exists where nums[j]=v; its sum = s – firstOccur[v]. Update ans.
  3. Record x for future:
     • If x not in firstOccur or firstOccur[x] > prev, set firstOccur[x] = prev.
• If ans stays –∞, return 0; else return ans.

Why It Works

• firstOccur[v] stores the smallest prefix sum before any position j with nums[j]=v.
• When at i, checking v=x±k finds the best possible start j, and sum = s_i – s_{j-1} in O(1).
• Single pass → O(n) time.

Step‑by‑Step on Example 2

nums = [-1,3,2,4,5], k=3
firstOccur = {}
s = 0, ans = –∞

i=0, x=-1: prev=0, s=-1
 check v=-1–3=-4, v=-1+3=2 → neither in map
 record firstOccur[-1]=0

i=1, x=3: prev=-1, s=2
 check v=3–3=0, v=3+3=6 → neither
 record firstOccur[3]=-1

i=2, x=2: prev=2, s=4
 check v=2–3=-1 → in map with 0 → candidate sum = 4–0=4
       v=2+3=5  → not in map
 ans = 4
 record firstOccur[2]=2

i=3, x=4: prev=4, s=8
 check v=4–3=1, v=4+3=7 → neither
 record firstOccur[4]=4

i=4, x=5: prev=8, s=13
 check v=5–3=2 → in map with 2 → sum = 13–2=11 → ans = max(4,11)=11
       v=5+3=8 → no
 record firstOccur[5]=8

end → ans=11 → return 11

Complexity Analysis

• Time: O(n) – one pass, O(1) per element
• Space: O(n) – hashmap of seen values

Python Code