Here is the algorithmic problem I'm trying to solve:Given a list of integers $x_1, x_2, \dots, x_n$ find a permutation $p_1, p_2, \dots, p_n \in [n]$ that maximises the sum $\sum_{i=1}^{n-1}|x_{p_{i+1}} - x_{p_i}|$.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 which are 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?
Finding a permutation $p$ of $x_1, x_2, \dots, x_n$ which maximises $\sum_{i=1}^{n-1}|x_{p_{i+1}}-x_{p_i}|$
ds.algorithms
This is not a complete answer, but it may be helpful.A piece of Mathematica code finds a counterexample of your greedy strategy: Consider the list of integers $\{51,54,55,70,98\}$. Your algorithm gives $\{98,51,70,54,55\}$ (Have I misunderstood your idea?) and the sum is 83. The program produces four permutations with the sum 125: $\{54, 98, 51, 70, 55\}, \{54, 70, 51, 98, 55\}, \{55, 98, 51, 70, 54\}, \{55, 70, 51, 98, 54\}$.It seems that you should put the maximal(s) between minimal(s) as far as possible. You can post other greedy strategies and prove (or disprove!) them by employing (maybe combining them) classic proof strategies such as mathematical induction, contradiction, and exchange argument.Edit:Actually, I don't quite understand why my answer (instead of that of @Marzio De Biasi) was accepted. Maybe the OP only want to know whether his/her greedy strategy is correct or not. Whatever, please refer to the answer of @Marzio De Biasi (and also other ones) for a complete solution.