Maximum Good Subarray Sum

Maximum Good Subarray Sum

What is this problem about?

The Maximum Good Subarray Sum coding problem defines a "good" subarray as one where the absolute difference between the first and last elements is exactly 1. Given an array of integers, you need to find the maximum possible sum of any such good subarray. This combines subarray sum optimization with a structural constraint on the endpoints, making it a layered problem that tests both prefix sum knowledge and hash table usage.

Why is this asked in interviews?

Companies like Google, Amazon, Zepto, Groww, and Atlassian favor this problem because it tests the ability to add constraints on top of a classical problem (maximum subarray sum). Pure dynamic programming won't work directly because of the endpoint condition. Candidates who can reformulate the problem using prefix sums and hash maps demonstrate the ability to adapt known techniques to novel constraints.

Algorithmic pattern used

The solution uses prefix sums with a hash table. Compute prefix sums as you iterate. For each index j, you want the minimum prefix sum at some index i where nums[i] and nums[j] differ by exactly 1, and i ≤ j. You maintain a hash map from each value to the minimum prefix sum seen at an index with that value. For each j, check the hash map for value nums[j]-1 and nums[j]+1, and compute the candidate sum as prefix[j] - minPrefix[neighbor]. Update the answer and update the hash map for nums[j].

Example explanation

Array: [1, 2, 1, 3]

• Prefix sums: [0, 1, 3, 4, 7]
• At index 1 (value=2): check value 1 → minPrefix[1]=0. Sum = prefix[2] - 0 = 3. Answer = 3.
• At index 2 (value=1): check value 2 → minPrefix[2]=1. Sum = prefix[3] - 1 = 3. Answer = 3.
• At index 3 (value=3): check value 2 → minPrefix[2]=1. Sum = prefix[4] - 1 = 6. Answer = 6.

The good subarray [2, 1, 3] has first=2, last=3, |2-3|=1, sum=6.

Common mistakes candidates make

• Using maximum prefix instead of minimum: You want to maximize subarray sum, which means subtracting the minimum prefix sum before index j.
• Not initializing prefix[0]=0: Missing the case where the good subarray starts from index 0.
• Forgetting both neighbors: Only checking nums[j]-1 but not nums[j]+1 misses valid good subarrays.
• Updating hash map before querying: Updating the map for nums[j] before checking it can incorrectly create subarrays of length 0.

Interview preparation tip

For the Array Hash Table Prefix Sum interview pattern, practice thinking of subarray sum problems as "prefix[j] - prefix[i]" and ask what constraint on index i you can look up in a hash map. This reformulation converts many constrained subarray problems into O(n) solutions. The "good subarray" endpoint condition maps naturally to hash map lookups by value.