In this problem, we are given a list of N numbers out of which K numbers are to be chosen such that the unfairness sum is minimized.
Let us define D as the unfairness sum of chosen K numbers.
First, we claim that k such numbers can only be obtained if we sort the list and choose k contiguous numbers. This can easily be proven. Suppose we choose numbers X1, X2, X3,....Xr, Xr+1,....,XK. All are in increasing order but not continuous in the sorted list, i.e. there exists a number p which lies between Xr and Xr+1. Now, if we include p and drop X1, our unfairness sum will decrease by an amount =
( |X1 - X2| + |X1 - X3| + .... + |X1 - XK| ) - ( |p - X2| + |p - X3| + .... + |p - XK| )
which is certainly positive. This shows that the solution will consist of k continuous elements of the sorted list. Now there exists (N-K+1) such sets of elements. The problem can be redefined as to find the minimum of the D obtained from all these sets.
First, we sort the list in increasing order: X1, X2, X3,....XK,XK+1,....,XN. The next step is to find the value of D for the first K elements i.e. from X1 to XK. suppose we have calculated D for first i elements. When we include Xi+1, the value of D increases by ( |Xi+1 - X1| + |Xi+1 - X2| +....+ |Xi+1 - Xi| ), which in turn is equal to ( i*XK - (X1 + X2 + ....+Xi) ). We just need to store the sum of the current elements and repeat the step for i = 1 to k-1.
Now that we have the solution for X1 to XK, we want to calculate the same for X2 to XK+1. This can be done in O(1) time.
New unfairness sum = old unfairness sum + ( |XK+1 - X2| + |XK+1 - X3| + .... + |XK+1 - XK| ) - ( |X1 - X2| + |X1 - X3| + .... + |X1 - XK| ). This can be written in the following form:
New unfairness sum = old unfairness sum + K.(XK - X1) - K.(X1 + X2 +....+XK) + ( X1 - XK)
At every point we just need to update the sum of the K elements, calculate the new unfairness sum and update the minimum value of the same.