有一个数组,其中包含从 0 到 999 的严格递增顺序的数字。
例如
int[] array = {0, 24, 55, 124, 200, 259, 400, 503, 666, 797};
我要做的是实现一个函数,该函数会选择 N 个数字,以使这些选择的数字之间的距离最小值最大化。
例如N为3,则取号为0、400、797,区间为400、397;所以返回值为 397(应该最大化)。如果我们选择其他数字组,则返回值将小于(或等于)397。
我想使用递归来实现它,但我很难编码。你愿意帮助我吗?
最佳答案
这个问题可以用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)的编程技术。
关于arrays - 选择数字以最大化间隔,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37240178/