Permutting a list of numbers in order to get a list which satisfies given condition

Question

Here is algorithmic problem I'm trying to solve:

Given a list [x_1,x_2,...,x_n] return a permutation of elements of the list [y_1,y_2,...,y_n] (where for each i we have y_i = x_j for only one j) which maximises the sum from k=1 to k=n-1 of |y_k-y_(k+1)|.

So to make it simpler - we get a list of integers and we need to "shuffle" these numbers in such a way, that we get a list where where we take sum of all |y_m-y_n| such that y_m and y_n are next to each other, we get a maximum possible number of all permutations of the elements in list.

I think this can be solved in O(n*log n), I thought of sorting the list and returning a list where first element is maximum element, next element is minimum, next is maximum of those left, etc... But this leads to nowhere, I cannot prove that it's correct, so probably it isn't. So, any tips how to tackle this problem?

Answer 1

Believe it or not, this problem is solvable in time O(n).

First, let m be the median of the array. For a pair (x, y) that are next to each other, define the contribution of x from that pair to be:

def contribution (x, y, m):
    if m < x:
        if x < y:
            return 0
        elif y < m:
            return x - m
        else:
            return x - y
    else:
        if y < x:
            return 0
        elif m < y:
            return m - x
        else:
            return y - x

This definition is kind of complex, but note that contribution(x, y, m) + contribution(y, x, m) == |x - y|. And the sum you are looking for is the sum of all of the contributions of all elements to both pairs.

The way to maximize the contribution of an element is to have it with elements on the other side of the median next to it on each side. What elements don't matter, just on the other side of the median. And the elements on the edge only do half their contribution, so it is clear that you want the two elements that are closest to the median on the ends. So this tells us exactly what the permutation that we want is. We want the two elements on the ends to be as close to the median as possible, while alternating above/below.

Now that we understand this, we can use http://en.wikipedia.org/wiki/Quickselect to find the median in O(n) time. Partitioning the array, and identifying the two elements to put on the end can then be done in O(n) time. And then interleaving it is also O(n) for a O(n) algorithm.