LeetCode 3026 - Maximum Good Subarray Sum

LeetCode Problem 3026

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Prefix Sum

Solution

Problem Understanding

The problem asks us to find the maximum possible sum of a contiguous subarray where the absolute difference between the first and last element of that subarray is exactly k.

More formally, for a subarray nums[i..j], it is considered good if:

$|nums[i]-nums[j]|=k$

We must examine all valid subarrays and return the largest subarray sum among them. If no such subarray exists, we return 0.

The input consists of:

• An integer array nums
• A positive integer k

The array can contain both positive and negative numbers. This detail is very important because the maximum good subarray is not necessarily the longest one. In fact, sometimes all valid subarrays may have negative sums.

The constraints are large:

• nums.length can be up to 10^5
• Each element can be as large as 10^9 in magnitude

These constraints immediately tell us that an O(n^2) solution will be too slow. We need something close to linear time.

There are several important edge cases:

• No good subarray exists, in which case we return 0
• All numbers are negative, where the answer may also be negative
• Multiple occurrences of the same value may produce many candidate subarrays
• The optimal subarray may start very early and end very late
• Prefix sums can become very large, so 64-bit integers are required

Because sums may exceed 32-bit integer range, both Python and Go implementations must carefully use large integer types.

Approaches

Brute Force Approach

The most straightforward solution is to examine every possible subarray.

For every starting index i, we try every ending index j >= i. For each subarray:

1. Check whether |nums[i] - nums[j]| == k
2. If it is good, compute its sum
3. Update the maximum answer

Using prefix sums, the subarray sum can be computed in O(1), but there are still O(n^2) subarrays overall.

This approach is correct because it explicitly checks every possible candidate. However, with n = 10^5, the number of subarrays becomes about 10^10, which is far too large.

Optimal Approach

The key observation is that the condition only depends on the first and last elements.

Suppose we are currently at index j with value nums[j].

A good subarray ending at j must start at some index i where:

$nums[i]=nums[j]-k\quad\text{or}\quad nums[i]=nums[j]+k$

Now consider the subarray sum:

$prefix[j+1]-prefix[i]$

To maximize this value for a fixed j, we want the smallest possible prefix[i].

This leads to the central idea:

• While scanning the array from left to right, store the minimum prefix sum seen before each value
• For the current number x, look for previously seen values x-k and x+k
• Use the stored minimum prefix sums to compute the best possible subarray sum ending at the current position

A hash map allows all lookups in constant time, producing an O(n) solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Checks every subarray using prefix sums
Optimal	O(n)	O(n)	Uses prefix sums and hash map for constant-time lookups

Algorithm Walkthrough

1. Initialize a running prefix sum.

The prefix sum represents the total of all elements processed so far. It allows us to compute any subarray sum efficiently. 2. Create a hash map called min_prefix.

For every value v, this map stores the minimum prefix sum seen before an occurrence of v.

This is the most important optimization. Since:

$subarray_sum=prefix[j+1]-prefix[i]$

maximizing the subarray sum means minimizing prefix[i]. 3. Iterate through the array from left to right.

At each position:

• Let the current number be x
• Let the current prefix sum before adding x be prefix

4. Before processing the current element, update the map entry for x.

If x has never appeared before, store the current prefix sum.

If it already exists, keep the smaller prefix sum.

This ensures we always retain the best possible starting position for future subarrays. 5. Add the current element to the running prefix sum. 6. Check whether x-k exists in the map.

If it does, then some earlier index contains value x-k, meaning the absolute difference condition is satisfied.

Compute:

$current_sum=prefix-min_prefix[x-k]$

Update the answer if this is larger. 7. Check whether x+k exists in the map.

This handles the opposite direction of the absolute difference. 8. Continue until the array is fully processed. 9. If no valid subarray was found, return 0.

Why it works

The algorithm works because every good subarray ending at index j must begin at an earlier index whose value differs from nums[j] by exactly k.

For each possible starting value, we store the minimum prefix sum before its occurrence. Since subarray sums are computed as a difference of prefix sums, using the minimum possible starting prefix automatically maximizes the subarray sum.

Thus, every valid subarray is considered implicitly, and the best one is selected.

Python Solution

from typing import List
from math import inf

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        min_prefix = {}
        
        prefix_sum = 0
        best = -inf
        
        for num in nums:
            if num not in min_prefix:
                min_prefix[num] = prefix_sum
            else:
                min_prefix[num] = min(min_prefix[num], prefix_sum)
            
            prefix_sum += num
            
            if num - k in min_prefix:
                best = max(best, prefix_sum - min_prefix[num - k])
            
            if num + k in min_prefix:
                best = max(best, prefix_sum - min_prefix[num + k])
        
        return 0 if best == -inf else best

The implementation follows the algorithm directly.

The dictionary min_prefix maps a value to the smallest prefix sum seen before that value appeared. This allows us to efficiently determine the best starting point for any future subarray.

The variable prefix_sum stores the running total of the array elements processed so far.

For each number:

1. We first store the current prefix sum for that value.
2. Then we include the current number in the prefix.
3. Finally, we check whether values num-k or num+k appeared earlier.

If either exists, we compute the corresponding subarray sum and update the answer.

The use of -inf helps distinguish between:

• No valid subarray found
• Valid subarrays with negative sums

Without this distinction, negative answers could be incorrectly replaced with 0.

Go Solution

package main

import "math"

func maximumSubarraySum(nums []int, k int) int64 {
	minPrefix := make(map[int]int64)

	var prefixSum int64 = 0
	best := int64(math.MinInt64)

	for _, num := range nums {
		if val, exists := minPrefix[num]; !exists {
			minPrefix[num] = prefixSum
		} else if prefixSum < val {
			minPrefix[num] = prefixSum
		}

		prefixSum += int64(num)

		if val, exists := minPrefix[num-k]; exists {
			candidate := prefixSum - val
			if candidate > best {
				best = candidate
			}
		}

		if val, exists := minPrefix[num+k]; exists {
			candidate := prefixSum - val
			if candidate > best {
				best = candidate
			}
		}
	}

	if best == int64(math.MinInt64) {
		return 0
	}

	return best
}

The Go solution mirrors the Python implementation closely.

The primary difference is integer handling. Since subarray sums can become very large, the implementation uses int64 for all prefix sums and answers.

The hash map stores:

map[int]int64

where:

• the key is the array value
• the value is the minimum prefix sum associated with that value

Go does not have built-in infinity values for integers, so math.MinInt64 is used as the sentinel for "no answer found yet".

Worked Examples

Example 1

Input:

nums = [1,2,3,4,5,6]
k = 1

Step	num	prefix before	map update	prefix after	candidate checks	best
1	1	0	map[1]=0	1	none	none
2	2	1	map[2]=1	3	check 1 → 3-0=3	3
3	3	3	map[3]=3	6	check 2 → 6-1=5	5
4	4	6	map[4]=6	10	check 3 → 10-3=7	7
5	5	10	map[5]=10	15	check 4 → 15-6=9	9
6	6	15	map[6]=15	21	check 5 → 21-10=11	11

Final answer:

11

Example 2

Input:

nums = [-1,3,2,4,5]
k = 3

Step	num	prefix before	prefix after	valid match	candidate	best
1	-1	0	-1	none	none	none
2	3	-1	2	none	none	none
3	2	2	4	-1 exists	4-0=4	4
4	4	4	8	none	none	4
5	5	8	13	2 exists	13-2=11	11

Final answer:

11

Example 3

Input:

nums = [-1,-2,-3,-4]
k = 2

Step	num	prefix after	valid match	candidate	best
1	-1	-1	none	none	none
2	-2	-3	none	none	none
3	-3	-6	-1 exists	-6	-6
4	-4	-10	-2 exists	-9	-6

Final answer:

-6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed once with O(1) hash map operations
Space	O(n)	The hash map may store every distinct value

The algorithm performs a single pass through the array. Every lookup and update in the hash map is expected constant time, so the overall complexity is linear.

The additional space comes from storing prefix information for distinct values. In the worst case, all numbers are unique.

Test Cases

sol = Solution()

# Provided examples
assert sol.maximumSubarraySum([1,2,3,4,5,6], 1) == 11  # increasing positives
assert sol.maximumSubarraySum([-1,3,2,4,5], 3) == 11  # mixed values
assert sol.maximumSubarraySum([-1,-2,-3,-4], 2) == -6  # all negatives

# No valid subarray
assert sol.maximumSubarraySum([1,1,1,1], 2) == 0  # no endpoints differ by 2

# Single valid subarray
assert sol.maximumSubarraySum([5,1], 4) == 6  # entire array valid

# Multiple occurrences of same value
assert sol.maximumSubarraySum([1,2,1,2,1], 1) == 7  # choose longest profitable range

# Large negative values
assert sol.maximumSubarraySum([-10,-20,-30], 10) == -30  # negative result retained

# Best subarray not shortest
assert sol.maximumSubarraySum([2,-1,2,3], 1) == 6  # [2,-1,2,3]

# Repeated prefix optimization
assert sol.maximumSubarraySum([4,-100,1,5], 1) == 6  # avoid bad early prefix

# Large k with no solution
assert sol.maximumSubarraySum([1,2,3], 100) == 0  # impossible difference

# Mixed positive and negative
assert sol.maximumSubarraySum([10,-5,7,3,-2,8], 2) == 21  # long profitable subarray

Test	Why
[1,2,3,4,5,6], k=1	Standard increasing sequence
[-1,3,2,4,5], k=3	Mixed positive and negative values
[-1,-2,-3,-4], k=2	Ensures negative answers are preserved
[1,1,1,1], k=2	No valid subarray exists
[5,1], k=4	Smallest valid array
[1,2,1,2,1], k=1	Repeated values and overlapping candidates
[-10,-20,-30], k=10	Entirely negative inputs
[2,-1,2,3], k=1	Optimal subarray is not shortest
[4,-100,1,5], k=1	Tests minimum prefix tracking
[1,2,3], k=100	Large impossible difference
[10,-5,7,3,-2,8], k=2	Mixed long-range optimal solution

Edge Cases

No Good Subarray Exists

If no pair of endpoints differs by exactly k, the answer must be 0.

This is important because many implementations initialize the answer to 0, which can accidentally hide valid negative answers. The implementation instead initializes the answer to negative infinity and only returns 0 if no valid subarray was ever found.

All Valid Subarrays Have Negative Sum

Consider:

nums = [-1,-2,-3,-4]
k = 2

The correct answer is -6, not 0.

A common bug is assuming the answer should never be negative. The algorithm correctly preserves negative results because it distinguishes between:

• "No solution"
• "Negative valid solution"

Multiple Occurrences of the Same Value

Suppose the same number appears many times.

A naive implementation might store only the latest occurrence, but that is not always optimal. We instead store the minimum prefix sum associated with that value.

This guarantees that whenever we form a subarray ending at the current index, we use the best possible starting position and maximize the resulting sum.