- Practice
- Algorithms
- Dynamic Programming
- Sherlock and Cost

# Sherlock and Cost

# Sherlock and Cost

In this challenge, you will be given an array and must determine an array . There is a special rule: For all , . That is, can be any number you choose such that . Your task is to select a series of given such that the sum of the absolute difference of consecutive pairs of is maximized. This will be the array's *cost*, and will be represented by the variable below.

The equation can be written:

For example, if the array , we know that , , and . Arrays meeting those guidelines 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
```

The maximum value obtained is .

**Function Description**

Complete the *cost* function in the editor below. It should return the maximum value that can be obtained.

cost has the following parameter(s):

*B*: an array of integers

**Input Format**

The first line contains the integer , the number of test cases.

Each of the next pairs of lines is a test case where:

- The first line contains an integer , the length of

- The next line contains space-separated integers

**Constraints**

**Output Format**

For each test case, print the maximum sum on a separate line.

**Sample Input**

```
1
5
10 1 10 1 10
```

**Sample Output**

```
36
```

**Explanation**

The maximum sum occurs when A[1]=A[3]=A[5]=10 and A[2]=A[4]=1. That is .