Minimisation of a distance sum I have a list $L$ of $N$ numbers, and I want to choose $k$ numbers $\{x_1,x_2, \ldots,x_k\}
\subseteq L$ in such a way value $S$ of the those K numbers is minimum.
$$
S = \sum_{0< i < j <= k} \left| x_i-x_j\right|  
$$

Suppose N=4 and list is {10,20,30,100} and K = 3.
Then we can choose {10,20,30} , {10,20,100} , {20,30,100} or {10,30,100}
I will prefer to choose first one because in that case value of is K is |10-20| + |20-30| + |30-10 | = 40 which is minimum among all selections.
Can we claim that if we sort the initial list then we will have to choose K consecutive elements of list.
 A: Yes.  Assume that $m$ and $p$ are in your chosen set and $n$ is in $L, m \lt n \lt p$ and not in the chosen set.  I claim that you can replace at least one of $m,p$ with $n$ and reduce the sum.  Continuing this, you can slide all the unused numbers out the end of the chosen list, reducing the sum along the way.  Let your chosen list have $r$ numbers less than $m$ and $s$ numbers greater than $p$.  Then if we replace $m$ with $n$ we change the sum by $r(n-m)-(s+1)(n-m)$ because we move $n-m$ units further away from $r$ numbers and the same distance nearer $s+1$ of them (including $p$).  Similarly, replacing $p$ with $n$ changes the sum by $-(r+1)(n-m)+s(n-m)$  Adding these gives $-2(n-m) \lt 0$, so at least one of them is negative.  Whichever one you removed now becomes a hole, and you can continue to move the hole in the same direction until it is no longer between two of your selected numbers.
A: The optimal choice of $k$ terms from $L$ will have no other terms strictly within their range. So an algorithm would be to 


*

*order $L$ from $l_1$ up to $l_N$, 

*let $s_n=\displaystyle\sum_{1 \le i \le k} (2 i -k - 1) l_{n+i-1}$ for $1\le n \le N-k+1$ (i.e. $S$ for $k$ successive terms from $L$ starting at the $n$th - an efficiency gain from recursion is possible in this calculation for different $n$),

*find the $m$ for which $s_m$ is lowest, and 

*select $\{l_m, l_{m+1},\ldots, l_{m+k-1}\}$  as your $k$ numbers from $L$ 


These minimse $S$ at the value $s_m$.
