Scale Engineer

Maximum Good Subarray Sum

Med
#2694Time: O(n^2). The nested loops iterate through all possible start and end points of subarrays, resulting in a quadratic number of pairs to check. The prefix sum calculation takes O(n), but it's dominated by the nested loops.Space: O(n). We need an auxiliary array of size `n+1` to store the prefix sums.3 companies
Patterns
Prefix Sum
Data structures
ArrayHash Table
Companies
AtlassianZeptoGroww

Prompt

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.

 

Example 1:

Input: nums = [1,2,3,4,5,6], k = 1
Output: 11
Explanation: The absolute difference between the first and last element must be 1 for a good subarray. All the good subarrays are: [1,2], [2,3], [3,4], [4,5], and [5,6]. The maximum subarray sum is 11 for the subarray [5,6].

Example 2:

Input: nums = [-1,3,2,4,5], k = 3
Output: 11
Explanation: The absolute difference between the first and last element must be 3 for a good subarray. All the good subarrays are: [-1,3,2], and [2,4,5]. The maximum subarray sum is 11 for the subarray [2,4,5].

Example 3:

Input: nums = [-1,-2,-3,-4], k = 2
Output: -6
Explanation: The absolute difference between the first and last element must be 2 for a good subarray. All the good subarrays are: [-1,-2,-3], and [-2,-3,-4]. The maximum subarray sum is -6 for the subarray [-1,-2,-3].

 

Constraints:

  • 2 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 1 <= k <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through all possible subarrays, checks if they are 'good', and calculates their sum to find the maximum. To optimize sum calculation, it uses a precomputed prefix sum array.

Algorithm

  • Create a prefix sum array prefix of size n+1, where prefix[i] stores the sum of elements from nums[0] to nums[i-1].
  • Initialize a variable maxSum to a very small value (e.g., Long.MIN_VALUE) and a boolean flag foundGoodSubarray to false.
  • Iterate through the array with a start index i from 0 to n-1.
  • For each i, iterate with an end index j from i+1 to n-1.
  • Check if the subarray nums[i..j] is good: if (Math.abs(nums[i] - nums[j]) == k).
  • If it's a good subarray, calculate its sum using the prefix sum array: currentSum = prefix[j+1] - prefix[i].
  • Update maxSum = Math.max(maxSum, currentSum) and set foundGoodSubarray to true.
  • After the loops, if foundGoodSubarray is true, return maxSum. Otherwise, return 0.

Walkthrough

The most straightforward way to solve this problem is to examine every possible subarray. A subarray is defined by its start and end indices, i and j.

We can use nested loops to generate all pairs of (i, j) where i < j. For each pair, we check if it forms a 'good' subarray by testing the condition |nums[i] - nums[j]| == k. If the condition is met, we then need to calculate the sum of the elements in nums[i..j].

A naive sum calculation for each good subarray would involve another loop, leading to an O(n^3) solution. We can optimize this by pre-calculating prefix sums. A prefix sum array, prefix, allows us to find the sum of any subarray nums[i..j] in O(1) time using the formula sum = prefix[j+1] - prefix[i]. This optimization reduces the overall time complexity to O(n^2).

We maintain a variable maxSum to keep track of the maximum sum found so far. Since the problem requires returning 0 if no good subarray exists, we use a boolean flag to track whether at least one has been found.

class Solution {    public long maximumSubarraySum(int[] nums, int k) {        int n = nums.length;        long[] prefix = new long[n + 1];        for (int i = 0; i < n; i++) {            prefix[i + 1] = prefix[i] + nums[i];        }         long maxSum = Long.MIN_VALUE;        boolean found = false;         for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                if (Math.abs((long)nums[i] - nums[j]) == k) {                    found = true;                    long currentSum = prefix[j + 1] - prefix[i];                    if (currentSum > maxSum) {                        maxSum = currentSum;                    }                }            }        }         return found ? maxSum : 0;    }}

Complexity

Time

O(n^2). The nested loops iterate through all possible start and end points of subarrays, resulting in a quadratic number of pairs to check. The prefix sum calculation takes O(n), but it's dominated by the nested loops.

Space

O(n). We need an auxiliary array of size `n+1` to store the prefix sums.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Inefficient for large inputs due to its quadratic time complexity, which will likely result in a 'Time Limit Exceeded' error on platforms with large test cases.

Solutions

public class Solution {    public long MaximumSubarraySum(int[] nums, int k) {        Dictionary < int, long > p = new Dictionary < int, long > ();        p[nums[0]] = 0 L;        long s = 0;        int n = nums.Length;        long ans = long.MinValue;        for (int i = 0; i < n; ++i) {            s += nums[i];            if (p.ContainsKey(nums[i] - k)) {                ans = Math.Max(ans, s - p[nums[i] - k]);            }            if (p.ContainsKey(nums[i] + k)) {                ans = Math.Max(ans, s - p[nums[i] + k]);            }            if (i + 1 < n && (!p.ContainsKey(nums[i + 1]) || p[nums[i + 1]] > s)) {                p[nums[i + 1]] = s;            }        }        return ans == long.MinValue ? 0 : ans;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem