0

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?

  • I'd say the beginning and end should contain the 2 middle numbers (the median and number closest to it) – ratchet freak Dec 13 '14 at 0:31
  • Why that should be the case? – qiubit Dec 13 '14 at 0:58
  • 1
    Because they are the ones closest to all the others, putting them at the ends eliminates one distance from each of them. your method can be improved simply by putting the last number you add to the beginning. – ratchet freak Dec 13 '14 at 1:52
4

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.