Maximum Good Subarray Sum - Practice Coding Problems

Maximum Good Subarray Sum - 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 the maximum sum of a good subarray of nums. If there are no good subarrays, return 0.

Input & Output

Example 1 — Basic Case

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

› Output: 11

💡 Note: The good subarray with maximum sum is [5,6] since |5-6|=1=k, and sum=5+6=11

Example 2 — No Good Subarrays

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

› Output: 11

💡 Note: Good subarray [2,4,5] where |2-5|=3=k, sum=2+4+5=11

Example 3 — Negative Numbers

$ Input: nums = [-1,-2,-3,-4], k = 2

› Output: -6

💡 Note: Good subarray [-3,-4] where |-3-(-4)|=1≠2, actually [-1,-3] where |-1-(-3)|=2=k, sum=-1+(-2)+(-3)=-6

Constraints

2 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹
1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,3,4,5,6] and k=1

Find Good Subarrays

Check all subarrays where |first-last|=k

Output

Return maximum sum among good subarrays

Key Takeaway

🎯 Key Insight: Use hash map to efficiently find matching start/end pairs that differ by exactly k

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is to use a hash map to efficiently find pairs of indices where the absolute difference equals k. The optimal approach tracks minimum prefix sums to maximize subarray sums. Best approach is hash map with min prefix tracking: Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Subarrays	O(n³)	O(1)	Check every possible subarray and find maximum sum among good ones
Prefix Sum with Hash Map	O(n²)	O(n)	Use prefix sums and hash map to efficiently find good subarrays
Optimized Hash Map with Min Prefix	O(n)	O(n)	Track minimum prefix sum for each value to maximize subarray sum

Brute Force - Check All Subarrays — Algorithm Steps

Generate all subarrays from index i to j
Check if |nums[i] - nums[j]| == k
Calculate sum and update maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Pairs

Try all (i,j) combinations

Check Condition

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

Calculate Sum

Sum elements from i to j and track maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

long long solution(int* nums, int numsSize, int k) {
    long long maxSum = 0;
    int found = 0;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i; j < numsSize; j++) {
            int diff = nums[i] - nums[j];
            if (diff < 0) diff = -diff;
            
            if (diff == k) {
                long long currentSum = 0;
                for (int l = i; l <= j; l++) {
                    currentSum += nums[l];
                }
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
                found = 1;
            }
        }
    }
    
    return found ? maxSum : 0;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    long long result = solution(nums, numsSize, k);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested loops to generate all pairs (i,j) and inner loop to calculate sum

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler