is this a dynamic programming problem

[mnnsa]

is this a dynamic programming problem
can you give some tips to solve this .....

You are given an array B of length N. You need to construct an array A of positive numbers such that A[i] <= B[i] for all 1 <= i <= N. The array A should be constructed in such a way that sum of absolute differences of consecutive pairs of A is maximized.

Let S =Σ |A[i] - A[i - 1]| for all 2 <= i <= N.

In other words, you need to construct array A of positive numbers such that S is maximized subject to condition A[i] <= B[i] for all 1 <= i <= N.

For example if the array B = [1, 2, 3]. We know A[1] <= 1, A[2] <= 2, A[3] <= 3. All arrays satisfying this condition are [1,1,1], [1,1,2], [1,1,3], [1,2,1], [1,2,2], [1,2,3] . Our calculations for the arrays are as follows:
|1-1| + |1-1| = 0
|1-1| + |2-1| = 1
|1-1| + |3-1| = 2
|2-1| + |1-2| = 2
|2-1| + |2-2| = 1
|2-1| + |3-2| = 2

There the maximum possible value of S is 2. Therefore the answer is 2.


Input Format
The first line of input consists of the number of test cases, T
The first line of each test case consists of the number of elements in B.
The second line of each test case consists of N space separated elements of B.


Constraints
1 <= N <=10^ 5
1 <= B[i] <= 100


Output Format
Print the maximum possible value of S.

Sample TestCase 1
Input
1
3
1 2 3
Output
2

[lastchance]

M(1,j) = 0
j=1,...,B(1)

Then
  M( n, j )    =     max{       M(n-1,i) + |j-i|    }      
j=1,...,B(n)     i=1,...,B(n-1)
successively for n = 2, ..., N


Answer is      max      { M(N,j) }
           j=1,...,B(N)

Maybe there's a more direct route. (EDIT: there is; see later).



Funny, though - if I do it for N=10⁵ randomly-generated elements I get remarkably little scatter around 5.8 million for an answer. Interesting problem in probability theory.

[mnnsa]

can you expalin it pls?

[lastchance]

mnnsa wrote:

can you expalin[sic] it pls?

But that would be giving you everything!

Dynamic programming, as you say. M(n,.) represents the maximum variation up to and including B(n) - it is computed from the previous array M(n-1,.).

There might be a quicker method: perhaps you only need to look at 1 and B(n) each time. Just trying that ...

For programming efficiency you only actually need to store two levels M(n,.) and M(n-1,.) at any one time.

[lastchance]

Actually there's a quicker route. You only need to look at bottom or top values (A(n)=1 or A(n)=B[n]) each time.

Start with Mlow = Mhigh = 0

Then loop for n = 2, ..., N:
  Oldlow = Mlow, Oldhigh = Mhigh
  Mlow = max( Oldlow, Oldhigh + |1-B(n-1)| )
  Mhigh = max( Oldlow + |B(n) - 1|, Oldhigh + |B(n)-B(n-1)| )    

Answer is max( Mlow, Mhigh )

On each loop, Mlow is the best variation you can get up to that point if you choose A(n)=1, whilst Mhigh is the best variation you can get up to that point if you choose A(n)=B(n).



If I run it six times with N=10⁵ rand()-generated elements then I end up with values that are remarkably close. Intriguing.

5824010
5814560
5833626
5829376
5811457
5817278

[mnnsa]

thanks, got it