For the sake of simplicity, let us determine ~N-K~ numbers which will remain in the array. This way we actually determine which ~K~ numbers should be removed.

Notice that there is always an optimal solution in which we choose ~N-K~ consecutive numbers in a sorted array.

Proof

Let ~a~ and ~b~ be the values of the greatest and the smallest chosen number in an optimal solution. Consider two cases:

1. If there does not exist an unchosen number ~c~ in the sorted array from the interval ~(a, b)~, a subsequence of consecutive elements is chosen and the proof is finished.

2. Else, determine which number out of ~a~ and ~b~ has the greater distance to the set of chosen numbers. We remove it, and pick ~c~ instead. The greatest absolute difference ~M~ is now decreased because ~b-c~ (or ~c-a~) is less than ~b-a~. By removing a number we have not increased the smallest absolute difference ~m~ because we have removed the greater of the two differences (distances). By adding ~c~, the difference of its two chosen neighbours in a sorted array is divided in two parts, so ~m~ is not increased this way. We have thus proved that each optimal solution can be reduced to the consecutive subsequence in a sorted array.

Here is a simple solution with a time complexity of ~\mathcal O(N^2)~ which sorts the array, for each of its substrings of the length ~N-K~ calculates the smallest and the greatest difference and returns the best solution. This solution is worth ~50\%~ of total points.

Notice that the greatest difference is actually the difference between the first and the last element of the substring and we can calculate it in a constant time complexity for each substring. If we keep the last ~N-K-1~ differences of consecutive array elements in a structure like a balanced binary tree, the smallest difference can be obtained in constant time complexity, but the operations of inserting and deleting have a logarithmic time complexity. This way we lower the complexity to ~\mathcal O(N \log N)~. This solution is worth ~70\%~ of total points.

Notice that the elements of the array are limited to the interval of ~R~ integers. We can therefore use a counting sort in the complexity of ~\mathcal O(N+R)~ to sort them. It is enough to calculate the frequency of each number in the interval and passing along the frequency array to generate a sorted array.

Let us take a look at the data structure we use to keep the differences of consecutive elements of the array. If the newly inserted difference is smaller than another difference in the structure, the other one will never be the smallest because it will be deleted before the newly inserted one. Therefore, the differences can be kept in a monotonous deque with two ends. The smallest difference in the substring will be the one at the beginning of the deque. Since ~N-1~ differences of consecutive elements will be inserted and deleted exactly once, we lower the time complexity to ~\mathcal O(N+R)~ and achieve full points.