arrays - 选择数字以最大化间隔

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。

我想使用递归来实现它，但我很难编码。你愿意帮助我吗？

Answer 1

这个问题可以用dynamic programing来解决.

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

然后我们可以将 s[c][p] 计算为 max for i=0..p of max(s[c-1][p-i], array[p] - 数组[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)的编程技术。