3026. Maximum Good Subarray Sum
Maximum Good Subarray Sum (LeetCode 3026) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
How to solve Maximum Good Subarray Sum
Maximum Good Subarray Sum is a Variable Size Sliding Window problem, part of Sliding Window. Master variable-size sliding window for condition-based problems like longest substring without repeating characters.
Work towards the solution in these steps:
- Save all the prefix sums into a HashMap.
- For the index <code>i</code> store the element at index <code>i + 1</code> as the key and the prefix sum till <code>i</code> as the value.
- For each prefix sum ending at <code>nums[i]</code>, try finding <code>nums[i] - k</code> and <code>nums[i] + k</code> in the HashMap and update the answer.
The reference solution runs in O(n log n) time and O(n) space.
The Maximum Good Subarray Sum solution and editorial walks through the full approach with reference code.
Problem statement
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
Topics and companies
Topics: Array, Hash Table, Prefix Sum.
How to practise Maximum Good Subarray Sum on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n log n) time and O(n) space.
Open Maximum Good Subarray Sum in the code editor, or read the Maximum Good Subarray Sum editorial for a worked solution with its approach and complexity analysis.
Where Maximum Good Subarray Sum sits in the DSA pattern sheet
Problems related to Maximum Good Subarray Sum
Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:
- Contains Duplicate II — Easy, same subpattern
- Continuous Subarrays — Medium, same subpattern
- Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
- Frequency of the Most Frequent Element — Medium, same subpattern
- Fruit Into Baskets — Medium, same subpattern
- Jump Game VII — Medium, same subpattern
Maximum Good Subarray Sum FAQ
What is the LeetCode number of Maximum Good Subarray Sum?
Maximum Good Subarray Sum is LeetCode problem 3026, rated Medium.
What pattern is used to solve Maximum Good Subarray Sum?
Maximum Good Subarray Sum is a Variable Size Sliding Window problem. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
What is the time complexity of Maximum Good Subarray Sum?
The reference solution runs in O(n log n) time and O(n) space.