查找大小为k的子集，使值之间的最小距离最大

Question

假设我有一个包含n整数的数组。
如何找到大小k的子集，使得子集中所有整数对之间的最小距离最大化，我的意思是它们在最远的距离。

示例：数组a[]={1,2,6,7,10}和k=3，
子集={1,6,10}，最小距离为10和6之间的4<错误的子集：
{1,7,10}，最小距离为3
{1,2,6}，最小距离为1

我想到了一个解决办法：

1） 排序数组2）选择一个[0]，现在在数组中查找ceil（a[0]x）=Y。。。。然后ceil（Yx）等k-1次，第k个元素也将a[n-1]

要查找x：
dp[i， j]是用于从第i个元素中选择j个元素的x。
最后我们想要dp[n][k]，它是x

但我在查找x时遇到了问题。

dp[i，j]=最大值（最小值（dp[k，j-1]，dp[i]-A[k]）
超过k=1到i-1，i=2到n，j=2到i

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

编辑：我想更正动态规划解决方案，尽管我知道可以通过对x进行二进制搜索来找到x。

更新2：我已经更新了代码，但仍然没有得到正确的解决方案。请指出错误
代码：http://ideone.com/J5vvR9

更新3：感谢@Gassa、@Niklas B.和@Fallen的回答！。




Answer 1

对X的值进行二进制搜索。然后为每个这样的X编写一个DP/贪婪函数，检查是否有一个数组的结果（元素之间的最大距离）大于或等于X。

正确性：如果对于任何一个X，我们可以有M个元素，使得它们之间的最小距离大于或等于X，那么对于每一个x，x

Answer 2

匿名用户

我认为如果时间允许搜索x的可能值，则无需查找x。只需添加外部循环，这将是对答案的二分查找（即，最小距离，让我们称之为x）。

一旦x被修复，您就可以贪婪地从a[0]开始选取值。下一个选择的值将是这样的值：a[i]，即i最小且a[i]-a[0]

总运行时间将为O（n log（C）），其中C是数组中可能值的总数。例如，如果数组中的整数从0到1000000，C将是1000001，log（C）（向上舍入）将是20。首先，您尝试x=500000；如果失败，则留给您答案的范围[0； 500000）；如果不是，则使用范围[500000； 1000000]等。

Answer 3

底座应为：

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

原因是空集的最小值是正无穷大。

在实践中，对于某些i和j，任何大于最大可能a[i]-a[j]的整数都足以作为INFINITY常量。

此外，正确的过渡是：

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