First sort the array. Then can be solved in O(n*k) using dp state as (i,k) which calculates the contribution of elements from i to n , given k out of K are chosen already before i. Contribution of element i is : (i) k*a[i] - (K - k)*a[i] if ith element isnt included in set I coz to the left of it we have k elements lesser and to the right we have (K - k) elements greater (ii) (i - 1 - k)*a[i] - (n - i - (K - k - 1))*a[i] if ith element is included in set I, coz to the left we have (i - 1 - k) elements that belongs to J, lesser than it and (n - i - (K - k -1)) elements to the right that belong to J