Max sum of abs difference in array
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 &lt; high; ++low, --high){
        maxSum += a[high] - a[low] + a[high] - a[low + 1];
    }
    maxSum += a[low] - a[0];
    return maxSum;
}