Max sum of abs difference in array

Question

I am just trying to understand the algorithm of the problem statement

Given an array, we need to find the maximum sum of absolute difference of any permutation of the given array.

Here is my implementation after following the algorithm mentioned in the link

static int sumOfMaxAbsDiff(int[] arr) {
    Arrays.sort(arr);
    int len = arr.length;
    int[] temp = new int[len];
    int sum = 0;
    for (int i = 0, j = 1, k = 0; i < len / 2; i++, j++, k++) {
      temp[k] = arr[i];
      temp[++k] = arr[len - j];
    }
    if (len % 2 != 0) { // Odd numbered length
      temp[len - 1] = arr[len / 2]; // copy the middle element of arr to last place in temp
    }
    // Now accumulate sum
    for (int i = 0; i + 1 < len; i++) {
      sum += Math.abs(temp[i] - temp[i + 1]);
    }
    // max abs diff at last index - NOT sure of this
    sum += Math.abs(temp[len - 1] - temp[0]); // assuming array size is >= 2
    return sum;
  }

I know why we have to sort, as we are trying to find max diff, it's obviously the least-highest If we arrange the sequence as firstSmallest, firstLargest, and so on for a given input arr [1,2,4,8] it would be [1,8,2,4] Now, checking the max diff in forward direction, max diff at each index, it would be 7,6,2,?

2 questions

1. For odd numbered length arr [1,2,3,4,8] why place middle at the end of arr?
2. And, for last index, why do we have to find abs difference between val at last index and first index?

Is there is any better and clear algorithm to think about or links to apply for this

Answer 1

For odd numbered length arr [1,2,3,4,8] why place middle at the end of arr?

The middle element in an odd numbered array, is the next highest element to be paired up. But since it is also the next lower element it doesn't have a pair, so it gets added by itself.

And, for last index, why do we have to find abs difference between val at last index and first index?

To my mind, the problem states 'maximum sum of absolute difference of any permutation'. The permutation of the lowest number on the high side of the sorted array and the lowest number wouldn't get added to the max sum otherwise.

Is there is any better and clear algorithm to think about

I believe there is. The idea of calculating the differences on the fly and adding to the max sum directly, has merit. It just needed tweaking a bit. Heres some working code for that concept:

static int MaxSumDifference2(int []a, int n) {
    Arrays.sort(a);
    int maxSum = 0;
    int low = 0;
    int high = a.length - 1;
    for(;low < high; ++low, --high){
        maxSum += a[high] - a[low] + a[high] - a[low + 1];
    }
    maxSum += a[low] - a[0];
    return maxSum;
}