- Dynamic Programming
- 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 .
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
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
For each test case, print the maximum sum on a separate line.
1 5 10 1 10 1 10
The maximum sum occurs when A=A=A=10 and A=A=1. That is .