Counterexamples to Claim that A = (10,1,1,10) for B = (10,1,1,10)?

[SlurrerOfSpeech]

I'm trying to solve a problem that amounts to:

Given b₀, ..., b_n-1 where1 <= b_i, find the max of |a₀ - a₁| + |a₁ - a₂| + ... + |a_n-2 - a_n-1| where 1 <= a_i <= b_i.

I'm 100% confident that each a_i is either 1 or b_i.

I'm 90% confident that the elements a₀, ..., a_n-1 are either

1, b₀, 1, b₁, ...,

or

b₀, 1, b₁, 1, ...

Are there any simple counterexamples?

 

[jedishrfu]

Can you give a context for your question? Is this some intuitive problem or is it based on some concrete example that someone might already know about?

 

[willem2]

Are there any simple counterexamples?

it's easy to see, that for all a_i-1 and a_i+1, a_i has to be 1 or b_i.
- if a_i is smaller than both a_i-1 and a_i+1, setting it to 1 will make the sum bigger.
- if a_i is biggger than both a_i-1 and a_i+1, setting it to b_i will make the sum bigger.
- if a_i is between a_i-1 and a_i+1 setting it to 1 or to b_i
will make the sum bigger.
The only case where the last possibility doesn't work, is when one of the neigbours is 1 and the other >= b. In that case the maximum sum is the same whatever a_i is.
You can force such a situation with a 1,2,3,1 sequence. a₁ can be anything <=2.
A non-conforming sequence with a larger sum of differences isn't possible.

 

[SlurrerOfSpeech]

Can you give a context for your question? Is this some intuitive problem or is it based on some concrete example that someone might already know about?

An algorithms problem I'm trying to solve https://www.hackerrank.com/challenges/sherlock-and-cost

The solution I tried is essentially

X = [1, b₀, 1, b₁, ... ]
Y =[b₀, 1, b₁, 1, ... ]
max(diffs(X), diffs(Y)]

and was surprised that it didn't pass all test cases.

 

[willem2]

To get the maximum, all a_i can be either 1 or b_i, but it doesn't have to be an alternating pattern of 1s and b_is.
B = (10,1,1,10) needs A = (10,1,1,10)