Maximise Function (MAXFUN) Solution — Codechef February Long Challenge

Problem Statement

You are given a sequence A1,A2,…,AN. Find the maximum value of the expression |Ax−Ay|+|Ay−Az|+|Az−Ax| over all triples of pairwise distinct valid indices (x,y,z).

Input

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

Output

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

Constraints

• 1≤T≤5
• 3≤N≤105
• |Ai|≤109 for each valid i

Subtasks

Subtask #1 (30 points): N≤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. For example, let x=1, y=2 and z=3, then it is |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.

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

Code (Solution)

The code has been implemented in Java

/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
long t = sc.nextLong();
      while(t-- > 0){
      int n = sc.nextInt();
      long arr[] = new long [n];
      for(int i=0;i<n;i++){
      arr[i] = sc.nextInt();
     }
     Arrays.sort(arr);
     long ax = arr[0];
     long az = arr[n-1];
     long temp=0,sum=0;
     for(int i=1;i<n-1;i++){
       temp = ( Math.abs(ax-arr[i]) + Math.abs(arr[i]-az) +                 Math.abs(az-ax) );
    if(temp>=sum){
       sum = temp;
   }
}
      System.out.println(sum);
   }
}
}

Hope you would have liked the article. Please give 50 claps to this article and follow me for more future programming related blogs.

References

https://www.codechef.com/FEB21C/problems/MAXFUN