Best Plus-Minus Stretch

Medium

You are given an integer array values. Pick a non-empty contiguous stretch values[i..j] and put alternating signs in front of its elements, starting with a plus: values[i] - values[i+1] + values[i+2] - .... Return the largest value of that expression over all stretches.

Example 1

values=[4, 6, -3, 2] → 11

The stretch [6, -3, 2]: 6 - (-3) + 2 = 11.

Example 2

values=[-5, -1] → -1

The stretch must be non-empty. The best is [-1] with value -1; [-5, -1] gives -5 - (-1) = -4.

Example 3

values=[1, 1, 1] → 1

Constraints

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

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium

Input

values=[4, 6, -3, 2]

Expected

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