Array Division solution codechef – Given a sequence XX of length MM, f(X)f(X) is defined as f(X)=∑M−1i=1|Xi+1−Xi|f(X)=∑i=1M−1|Xi+1−Xi|.

For e.g., f([3,1,7,2])=|1−3|+|7−1|+|2−7|=13f([3,1,7,2])=|1−3|+|7−1|+|2−7|=13

JJ has an array AA of length NN. He wants to divide the array AA into two subsequences PP and QQ (possibly empty) such that the value of f(P)+f(Q)f(P)+f(Q) is as large as possible. (Note that each AiAi must belong to either subsequence PP or subsequence QQ).

Help him find this maximum value of f(P)+f(Q)f(P)+f(Q).

Note: A sequence XX is a subsequence of a sequence YY if XX can be obtained from YY by deletion of several (possibly, zero or all) elements.

Array Division solution codechef

• The first line contains TT – the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer NN – the size of the array AA.
• The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN denoting the array AA.

Output Format

Output the largest value of f(P)+f(Q)f(P)+f(Q).

Constraints

• 1≤T≤2001≤T≤200
• 1≤N≤10001≤N≤1000
• 1≤Ai≤1051≤Ai≤105
• It is guaranteed that the sum of NN over all test cases does not exceed 30003000.

Array Division solution codechef

 

3
6
1 4 6 3 4 2
5
1 2 3 4 5
2
1 10

Sample Output 1 

11
6
9

Array Division solution codechef

Test case-1: One way to divide the array into two subsequences PP and QQ as follows:

P=[1,6,2]P=[1,6,2], Q=[4,3,4]Q=[4,3,4].

f(P)=|6−1|+|2−6|=9f(P)=|6−1|+|2−6|=9 and f(Q)=|3−4|+|4−3|=2f(Q)=|3−4|+|4−3|=2.

Therefore f(P)+f(Q)=11f(P)+f(Q)=11.

It can be proven that this is the maximum value of f(P)+f(Q)f(P)+f(Q).

Test case-2: One way to divide the array into two subsequences PP and QQ as follows:

P=[1,4]P=[1,4], Q=[2,3,5]Q=[2,3,5].

f(P)=|4−1|=3f(P)=|4−1|=3 and f(Q)=|3−2|+|5−3|=3f(Q)=|3−2|+|5−3|=3.

Therefore f(P)+f(Q)=6f(P)+f(Q)=6.

It can be proven that this is the maximum value of f(P)+f(Q)f(P)+f(Q).

Test case-3: One way to divide the array into two subsequences PP and QQ as follows:

P=[1,10]P=[1,10], Q=[]Q=[].

f(P)=|10−1|=9f(P)=|10−1|=9 and f(Q)=0f(Q)=0.

Therefore f(P)+f(Q)=9f(P)+f(Q)=9.

It can be proven that this is the maximum value of f(P)+f(Q)f(P)+f(Q).