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
y_i = x_jfor only one
j) which maximises the sum from
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_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?