Suppose i have an array which contain n
integers .
How to find subset of size k
such that the minimum
distance between all pairs of integers in the subset is maximized
, i mean they are at farthest distance .
example : array a[]={1,2,6,7,10}
and k=3
,
subset = {1,6,10}
, the minimum distance is 4
between 10 and 6 .
Wrong subsets :
{1,7,10}
, minimum distance is 3
{1,2,6}
, minimum distance is 1
I came up with a solution :
1) sort array
2) select a[0] , now find ceil(a[0]+ x
) = Y in array ....and then ceil(Y+ x
) and so on k-1
times , also kth element will be a[n-1]
To find x
:
dp[i,j]
be the x
for selecting j elements from first i elements .
Finally we want dp[n][k]
which is x
But i am facing problem in finding x
.
dp[i,j] = max( min( dp[k,j-1], dp[i]-A[k] ) )
over k=1 to i-1 , i=2 to n , j=2 to i
dp[i][1] = 0 over i = 1 to n
EDIT : I want to correct the dynamic programming solution , though i know x can be found out by binary searching over x .
UPDATE 2 : I have updated the code , but still not getting correct solution . Please point the error .
code : http://ideone.com/J5vvR9
UPDATE 3 : Thanks @Gassa , @Niklas B. and @Fallen for your answers !.