Maximum Sum Desirable Subarray
Problem statement
Given an integer array values and a non-negative integer k, call a non-empty contiguous subarray desirable when the absolute difference between its first and last values is exactly k.
Return the maximum sum of a desirable subarray as a decimal string. Return IMPOSSIBLE when no desirable subarray exists.
Function
maximumDesirableSubarraySum(values: long[], k: long) → StringExamples
Example 1
values = [10,20,30,40]k = 20return = "90"The subarray [20,30,40] has endpoint difference 20 and sum 90, which is maximal.
Example 2
values = [-5,10,-2]k = 0return = "10"Every one-element subarray has equal endpoints. The best one contains 10.
Example 3
values = [1,2,3,4]k = 5return = "IMPOSSIBLE"No two endpoints differ by 5, and a one-element subarray differs by 0.
Constraints
- The array contains between 1 and 200000 values.
- Every array value is between -10^9 and 10^9.
kis between 0 and 10^9.- The maximum possible subarray sum fits in a signed 64-bit integer.
Source note: Author-written prompt excerpt retained for source fidelity.