One Reversal for Maximum Roughness

Hard

The roughness of an array is the sum of absolute differences between neighbors: |values[0] − values[1]| + |values[1] − values[2]| + … + |values[n−2] − values[n−1]|. You are given an integer array values. You may, **at most once**, pick a contiguous subarray and reverse it. Return the largest roughness you can achieve.

Example 1

values=[1, 5, 6, 2] → 13

The roughness is now 4 + 1 + 4 = 9. Reverse the opening [1, 5] to get [5, 1, 6, 2], worth 4 + 5 + 4 = 13.

Example 2

values=[1, 2, 3, 4] → 5

Reverse [1, 2, 3]: the array [3, 2, 1, 4] gives 1 + 1 + 3 = 5.

Example 3

values=[5, 5, 5] → 0

All numbers are equal, so no reversal can lift the roughness above zero.

Constraints

2 ≤ len(values) ≤ 3 · 10⁴
-10⁵ ≤ values[i] ≤ 10⁵
The answer fits in a signed 32-bit integer

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Math

Similar problems

Cloning Builders Hard Biggest Number Divisible by Three Hard Split Numbers Into Order Hard Growing Groups Without Repeats Hard Word Topping Duel Hard

Input

values=[1, 5, 6, 2]

Expected

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