找到两点之间的最大距离

Question

昨天,我出现在一次采访中.我陷入了其中一个问题,我在这里问的是同样的问题.

有一个给出的数组显示x轴上的点,有N个点.和M币也给了.

Remember N >= M

您必须最大化任意两点之间的最小距离.

Example: Array : 1 3 6 12
         3 coins are given.
         If you put coins on 1, 3, 6 points Then distance between coins are : 2, 3 
         So it gives 2 as answer 
         But we can improve further
         If we put coins at 1, 6, 12 points.
         Then distances are 5, 6
         So correct answer is : 5

请帮帮我,因为我完全陷入了这个问题.

Answer 1

您可以使用贪婪算法：选择有序序列的第一个和最后一个点（因为这是最大可能的距离）。然后，您选择最接近它们平均值的点（因为任何其他答案都会在一侧给出较小的距离），而不是选择较大的分区。然后根据需要重复多次。