Best Span With a Fixed End Gap

Medium

You get an integer array values and a positive integer gap. Call a contiguous segment values[i..j] (with i < j) fitting if its two end elements differ by exactly gap: |values[i] - values[j]| == gap. Return the largest element sum over all fitting segments. If no segment fits, return 0. The sum may turn out negative.

Example 1

values=[3, -2, 8, 6, 1], gap=5 → 9

Two segments qualify: [3, -2, 8] (|3 − 8| = 5, sum 9) and [6, 1] (|6 − 1| = 5, sum 7). The best sum is 9.

Example 2

values=[4, 4, 4], gap=2 → 0

All elements are equal, so the ends always differ by 0. No segment qualifies, and the answer is 0.

Example 3

values=[-5, -9, -2, -7], gap=4 → -14

Constraints

2 ≤ len(values) ≤ 10⁵
-10⁹ ≤ values[i] ≤ 10⁹
1 ≤ gap ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Prefix Sum

Similar problems

Longest Run with a Given Sum Medium A Stretch Divisible by k Medium As Many Heads as Tails Medium Stretches With an Exact Total Medium Windows With an Exact Alarm Count Medium

Input

values=[3, -2, 8, 6, 1], gap=5

Expected

Run checks the first 3 tests in your browser. Submit checks all 104 tests on the server, hidden ones included.