Find a subset of size k so that the minimum distance between the values ​​is the maximum

Question

Suppose I have an array containing nintegers.
How to find a subset of size k, so that the distance minimumbetween all pairs of integers in the subset maximized, I mean that they are at the farthest distance.

Example array a[]={1,2,6,7,10}and k=3,
subset = {1,6,10}the minimum distance 4between 10 and 6.
Irregular subsets :
{1,7,10}the minimum distance 3
{1,2,6}, the minimum distance1

I came up with a solution:

1) sort the array
2) select [0], now find ceil (a [0] + x) = Y in the array .... and then ceil (Y + x), etc. k-1times, also the kth element will bea[n-1]

Find x:
dp[i,j]will be xto select j elements from the first i elements.
Finally, we want dp[n][k]whichx

But I ran into a search problem x.

dp [i, j] = max (min (dp [k, j-1], dp [i] -A [k]))
                over k = 1 - i-1, i = 2 - n, j = 2 - i

dp [i] [1] = 0 over i = 1 to n

EDIT . I want to fix a dynamic programming solution , although I know that x can be detected by binary search on x.

2. , . . : http://ideone.com/J5vvR9

3: @Gassa, @Niklas B. @Fallen !

Answer 1

:

dp[i][1] = INFINITY for i = 1 to n

, , .

, a[i] - a[j] i j, INFINITY.

, :

dp[i,j] = max{for k=1 to i-1} (min(dp[k,j-1], a[i]-a[k]))

Answer 2

, x, x. , (.. , x).

x , a[0]. a[i], i a[i] - a[0] >= x. a[j] , j a[j] - a[i] >= x .. k , , , x; , x.

O (n log (C)), C - . , 0 1000000, C 1000001, log (C) () 20. x = 500000; , [0; 500000) ; , [500000; 1000000] ..

Answer 3

X. x DP/Greedy, , ( ), X.

Correctness . If for any X we can have M elements, so that the minimum distance between them is greater than or equal to X, then for each x, x <X, at least the same array will be the server as a result. And for any X, if there are no M elements, such that the minimum distance between the elements is greater than or equal to X, then for no x, x> X, M such elements are available. So we can binary search on X.