Maximise Function Codechef February Challenge Hint and Solution

 

Maximise Function Problem Code: MAXFUN

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$

$\mathrm{<br>}$

HINT:

1.sort the given array

2.store x=arr[0]  z=arr[n-1]  ans=0

3.use for loop from 1 to n-1 ans calculate the given function value into variable ans take maximum answer ans=max(ans,F)  F is variable in which you'll calculate the value

Still not understand then take this is as F value hope you'll grab this hint

$\mathrm{}$

F=(abs(x-arr[i])+abs(arr[i]-z)+abs(z-x));