选择数字以最大化间隔

Question

有一个数组，严格按照从0到999的顺序包含数字。

例如：

int[] array = {0, 24, 55, 124, 200, 259, 400, 503, 666, 797};

我需要做的是实现一个函数，它选择N个数字，以便这些选定数字之间的最小距离值最大化。

例如，如果N为3，则选定的数字为0、400和797，间隔分别为400和397；因此返回值为397（应该最大化）。如果我们选择其他数字集合，则返回值将小于（或等于）397。

我想使用递归来实现它，但我很难编写代码。你能帮我吗？

- 23thMay

---

$n$ 的限制是多少？你期望的复杂度是什么？你尝试过什么？ - advocateofnone

这个问题已经解决了。请参考下面的帖子 找到大小为k的子集，使得值之间的最小距离最大。 - Ayoub Falah

如果N为3，则必须选择第一个元素、最后一个元素和最靠近中间点的元素，这是一种二分查找，因此时间复杂度为O(log(n))。 对于更高的N可能有类似的情况。 - Gabriel Furstenheim

你能帮帮我吗？有些人可能更愿意帮忙，如果你展示一下你尝试过的（在这里指你没有成功编码的想法）。我想使用递归来实现它。那么什么是基本情况？如何将一个大问题实例缩小到更小的问题实例，并如何将小问题的解决方案组合成大问题实例的解决方案？（而且我不明白“_23thMay_”是什么意思？） - greybeard

Answer 1

这个问题可以使用动态规划来解决。

如果我们定义s[c][p]为选择c个数字且在输入数组中最后选择的数字的索引为p时的解决方案。

我们可以计算s[c][p]为max for i=0..p of max(s[c-1][p-i], array[p] - array[p-i]) 在开始时，以下状态：s[1][0..n]，其中n是输入数组的长度，应该具有值0。

拥有s[1][0..n]，我们现在可以轻松地计算s[2][0..n]，使用给定的公式。
拥有s[2][0..n]，我们现在可以轻松地计算s[3][0..n]。
以此类推...

整个问题的解决方案将是max s[N][N-1..n]，其中n是输入数组的长度，N是要选择的数字数量。

此解决方案的时间复杂度为O(N*n^2)。
解释：我们计算s[0..N][0..n]的值，每次计算的时间复杂度为O(n)。

此解决方案的内存复杂度为O(n)。
解释：为了计算s[c][0..n]，您只需要s[c-1][0..n]，因此在任何时刻实际上只需要2*n的内存。

编辑：您可以使用递归来实现所描述的算法，使用称为记忆化的编程技术（https://en.wikipedia.org/wiki/Memoization）。

- Nemanja Trifunovic