Maximise Function codechef February 2021 long challenge editorial

 Maximize Function codechef February 2021  long challenge editorial -

Problem Statement- 

You are given a sequence A1,A2,…,AN$A_1,A_2,\dots ,A_N$. Find the maximum value of the expression |Ax−Ay|+|Ay−Az|+|Az−Ax|$|A_x-A_y|+|A_y-A_z|+|A_z-A_x|$ over all triples of pairwise distinct valid indices (x,y,z)$(x,y,z)$.

Input

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains a single integer N$N$.
• The second line contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$.

Output

For each test case, print a single line containing one integer ― the maximum value of |Ax−Ay|+|Ay−Az|+|Az−Ax|$|A_x-A_y|+|A_y-A_z|+|A_z-A_x|$.

Constraints

• 1≤T≤5$1\le T\le 5$
• 3≤N≤105$3\le N\le {10}^5$
• |Ai|≤109$|A_i|\le {10}^9$ for each valid i$i$

Subtasks

Subtask #1 (30 points): N≤500$N\le 500$

Subtask #2 (70 points): original constraints

Example Input

3
3
2 7 5
3
3 3 3
5
2 2 2 2 5

Example Output

10
0
6

Explanation

Example case 1: The value of the expression is always 10$10$. For example, let x=1$x=1$, y=2$y=2$ and z=3$z=3$, then it is |2−7|+|7−5|+|5−2|=5+2+3=10$|2-7|+|7-5|+|5-2|=5+2+3=10$.

Example case 2: Since all values in the sequence are the same, the value of the expression is always 0$0$.

Example case 3: One optimal solution is x=1$x=1$, y=2$y=2$ and z=5$z=5$, which gives |2−2|+|2−5|+|5−2|=0+3+3=6$|2-2|+|2-5|+|5-2|=0+3+3=6$.

Solution-

Hint - Sort the array.

Solution will be posted anytime soon stay connect .

Must join Telegram channel -https://t.me/competitiveProgrammingDiscussion

explore our other products: Free SIP calculator tool