Katkat
Back

Maximize Boundary-Difference Subarray Sum

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates algorithmic problem-solving skills with emphasis on array processing, constrained subarray sums, and the design of time- and space-efficient algorithms within the Coding & Algorithms domain.

Given an integer array nums and an integer k, find the maximum possible sum of a non-empty contiguous subarray whose first and last elements differ by exactly k in absolute value.

A subarray nums[l..r] is valid if:

abs(nums[l] - nums[r]) == k

Return the maximum sum among all valid subarrays. If no valid subarray exists, return 0.

Example 1:

Input: nums = [1, 2, 3, 4, 5], k = 3
Output: 14
Explanation: The subarray [2, 3, 4, 5] has endpoints 2 and 5, whose absolute difference is 3, and its sum is 14.

Example 2:

Input: nums = [-1, 3, 2, 4, 5], k = 3
Output: 11
Explanation: The subarray [2, 4, 5] has endpoints 2 and 5, whose absolute difference is 3, and its sum is 11.

Example 3:

Input: nums = [5, 1, 8], k = 10
Output: 0
Explanation: There is no valid subarray.

Constraints:

1 <= nums.length <= 100000
-1000000000 <= nums[i] <= 1000000000
0 <= k <= 1000000000

Design an algorithm efficient enough for the given constraints.