3026. Maximum Good Subarray Sum

https://leetcode.com/problems/maximum-good-subarray-sum/description/

First, I thought this is intuitive and this would be the optimal solution

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        long long max_sum = LLONG_MIN;
        bool found = false;
        for(int i=0;i<n;i++){
            long long currSum = nums[i];
            for(int j=i+1;j<n;j++){
                currSum+=nums[j];
                if(abs(nums[i] - nums[j])==k){
                    max_sum = max(currSum,max_sum);
                    found=true;
                }
            }
        }
        return found ? max_sum : 0;
    }
};

However the above code gives TLE - only 777 / 782 test cases passed as it is O(n^2)

Thus we have to think of an optimised solution

If |nums[i] - nums[j]| == k, then either:

• nums[i] = nums[j] + k, or
• nums[i] = nums[j] - k

Strategy: For each ending position j, check if we’ve seen the required starting values before!

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> prefixSum(n + 1, 0);
        
        // Build prefix sum array
        for(int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        // Map: value -> minimum prefix sum seen so far for that value
        unordered_map<int, long long> minPrefixForValue;
        long long maxSum = LLONG_MIN;
        bool found = false;
        
        for(int j = 0; j < n; j++) {
            // Check if we can form a good subarray ending at j
            int target1 = nums[j] + k;  // nums[i] should be nums[j] + k
            int target2 = nums[j] - k;  // nums[i] should be nums[j] - k
            
            // Check both possible starting values
            if(minPrefixForValue.count(target1)) {
	            // prefixSum[i] -> get from the hashmap
	            //prefixSum[j+1] - prefixSum[i]
                long long subarraySum = prefixSum[j + 1] - minPrefixForValue[target1];
                maxSum = max(maxSum, subarraySum);
                found = true;
            }
            
            if(minPrefixForValue.count(target2)) {
		        //prefixSum[j+1] - prefixSum[i]
                long long subarraySum = prefixSum[j + 1] - minPrefixForValue[target2];
                maxSum = max(maxSum, subarraySum);
                found = true;
            }
            
            // Update minimum prefix sum for current value
            if(!minPrefixForValue.count(nums[j]) || prefixSum[j] < minPrefixForValue[nums[j]]) {
                minPrefixForValue[nums[j]] = prefixSum[j];
            }
        }
        
        return found ? maxSum : 0;
    }
};
 

Minimize Starting Prefix: To maximize subarray sum, we store the minimum prefix sum for each value (since we subtract it)

🎯 The Condition Breakdown

if(!minPrefixForValue.count(nums[j]) || prefixSum[j] < minPrefixForValue[nums[j]]) {
    minPrefixForValue[nums[j]] = prefixSum[j];
}

This has two parts:

1. !minPrefixForValue.count(nums[j]) → Haven’t seen this value before
2. prefixSum[j] < minPrefixForValue[nums[j]] → Current prefix is smaller than stored one

🧠 Why Store the MINIMUM Prefix Sum?

Key Insight: To maximize subarray sum, we want to minimize what we subtract!

Subarray sum formula: prefixSum[j+1] - prefixSum[i]

To maximize this, make prefixSum[i] as small as possible.

thus we store the minimum prefix sum for that value as we iterate

if(!minPrefixForValue.count(nums[j]) || prefixSum[j] < minPrefixForValue[nums[j]]) {
    minPrefixForValue[nums[j]] = prefixSum[j];
}