Endpoint Difference Subarray
MediumHash Map · Amazon
Given an integer array nums and a non-negative integer k, consider every contiguous subarray nums[i..j] with i < j (so it has at least two elements) whose endpoints satisfy |nums[i] - nums[j]| == k. Call such a subarray good.
Return the maximum sum of a good subarray. The maximum may be negative. If no good subarray exists, return 0.
Example 1
- Input:
- nums = [3, -1, 4, 1, 5, -9, 2], k = 2
- Output:
- 12
- Explanation
- Pairs of endpoints differing by 2 include (3, 1), (3, 5) and (-1, 1). The best is
[3, -1, 4, 1, 5]from index 0 to 4, with endpoints 3 and 5 and sum 12.
Example 2
- Input:
- nums = [-4, -6, -2, -8], k = 2
- Output:
- -10
- Explanation
- The good subarrays are
[-4, -6](sum -10),[-4, -6, -2](sum -12) and[-6, -2, -8](sum -16). The best sum is negative, and it is still returned.
Example 3
- Input:
- nums = [1, 1, 1], k = 5
- Output:
- 0
- Explanation
- No two elements differ by 5, so there is no good subarray and the answer is 0.
Constraints
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^90 <= k <= 10^9