我要寻找的总体思路的一种算法来解决以下问题有所帮助。该问题已转让了给我。它看起来像它应该是可以解决的，通过一个贪婪的方法，但我不能想出一个简单的解决方案。这里的问题说明：

您给出序列的 N 号 A_1 ... A_N ，使得 0 = A_1＆LT; A_2＆LT; ...＆LT; A_N 。你必须消除的最多的这些数字中的 M ，使得最小差值 A_I + 1 - A_I 之间的任何两个连续的数量最大化。

您可能无法消除的第一个和最后一个元素， A_0 和 A_N 。你也必须消除的几个数字是可能的：如果取消 M - -1 你得到的最短距离为 D 和消除 M 你仍然有相同的最小差异，你不能消除此最后一个数字。

我不要求一个完整的解决这个问题。只有少数的指引，算法如何看起来。

编辑：有些测试样品。请记住，可能有多个有效的解决方案。

 从删除最多7：
0 3 7 10 15 18 26 31 38 44 53 60 61 73 76 80 81 88 93 100

解：
0 7 15 26 31 38 44 53 60 73 80 88 93 100
 

 从删除最多8：
0 3 7 10 15 26 38 44 53 61 76 80 88 93 100

解：
0 15 38 53 76 88 100
 

解决方案

下面是一个确切的 O（NM ^ 2） - 时间，O（NM）空间的动态规划算法得到正确的答案上以毫秒为单位的所有业务方案的例子。其基本思路是：

每当我们施加的特定数量应的不的被删除时，它形成两个子之间的栅栏以这样的方式，解决每个子最佳地保证向整个问题的最佳解决方案的约束与约束不到位， 每个最优解必须以一个非删除数，接着连续删除号码一些数，后跟一个非删除数，随后对这个问题的其余部分的最佳解决方案，开始于第二非删号并使用适当降低米

在下文中，x [i]于装置列表中的第i个数字，具有从0开始的索引

递归

令f（I，J）是最佳的（最大的最小）间隔尺寸从号码列表的后缀获得起始于位置0℃= I＆其中; N的保持这种（即第i个）的数量和删除完全后（不一定是连续的）数字第j。下面的递归显示了这是如何计算的：

  F（I，J）= MAX（G（I，J，D））对所有0℃= D＆LT; =分钟（J，镍2）
克（I，J，D）=分钟（×〔1 + D + 1]  -  X [I]中，f（1 + D + 1，J-d））的
 

在分（J，镍2）在那里，而不是只是普通的J确定prevent缺失过去的终结。我们唯一需要的基础案例有：

的 F（N-1，0）=无穷大（这具有使效果分钟（F（N-1），0）中，z）= z）的
F（N-1，J＆0）= 0（此情况下，仅出现如果M将N  -  2）
 

工作原理

在更详细地，计算F（I，J），我们做的是循环遍历所有可能的数字（包括0）的连续删除起始位置i + 1，在每种情况下计算的最低的（a）该间隔通过缺失该块和（b），以开始对第一个未删除编号以该块的右侧的子问题的最优解而形成的。 是非常重要的规定，在第一号的块（X [I]）不会被删除，从而使previous（父）子问题的区间始终是封顶。的这是一个棘手一部分我花了一段时间才能体现出来。

使其快速

如果您code可高达普通递归它上面会工作，但它需要时间指数在M和N通过的 memoising F（），我们保证它的身体将至多N * M次（每个不同的参数组合一次）运行。每个功能运行时，它的时间，通过缺失越来越长块执行O（M）工作的扫描，为O（NM ^ 2）总时间。

您无法通过使用更少的缺失造成了较大的差距，因此整体的最大最小间隔的大小可以通过翻翻M + 1的结果F（0，M），F（0，M-1）可以发现，.. 。中，f（0,0），用于所述第一数目是比previous数小：即previous数为答案，而且第二个参数到f（）是必需的缺失的最小数目。为了找到最佳的解决方案（即删除特定号码的列表），您可以记录在一个单独的predecessor阵作出的决定，使得p [I，J]给出d的值（可变成$ P $ i和j pvious值），导致对于f（I，J）的最优解。 （也许是predecessor是混淆这里：它指的是解决了子问题的在的当前的子问题，虽然这些子问题出现后（或右侧）的后缀重presenting当前的子问题。）这些环节之后可来恢复删除/鸵鸟政策删除作出的决定。

工作C ++ code

http://ideone.com/PKfhDv

附录：早期的失误

通过这样的一个棘手的问题，它可以帮助一下错误的方法，看看到底哪里出了问题...： - /我想我解决了这个问题，但我没有注意到的要求返回使用尽可能少的缺失越好，我最初尝试解决这个问题没有工作的解决方案。

一开始我尝试定义F（I，J）是最佳（最大最小）区间大小从号码列表的后缀获得的​​起始位置，0℃= I＆LT; N的保持这种（即第i个）的数量和删除的 0的任何地方最多的J 的后面（不一定是连续的）数字。但是，这造成了微妙的问题：这不一定，你可以装到这个最佳的解决方案，从最优解子问题的情况下。我最初以为这可能是固定通过改变函数返回一个（间隔大小，以实现这一区间大小需要删除的最小数量）对，而不是只是一个间隔大小，并让它打破共享最大最小间隔操作之间的关系通过总是选择最小化的缺失的数量的作用大小。但是，这不是一般的真，因为最佳的解决子间（即与数表的某些后缀）将花费缺失使得在该区域中的最小间隔尺寸尽可能大，即使这些缺失变成被浪费因为完整的解决方案的preFIX将迫使整体最小反正要低一些。下面是使用一个f（）返回（间隔大小，达到该大小需要删除的最小数量）对一个反例：

 问题：M = 1，X = [10 15 50 55]。

F（2,0）=（5,0）（留下[50 55]）
F（1,1）=（40，1）（删除50离开[15 55]）; *本地*这似乎更好
          不是不删除任何内容，这将使[15 50 55]和产量
          最小 - 间隙5，即使后者将是一个较好的选择
          整个问题）
F（0,1）=最大（分钟（5中，f（1，1）），分钟（40中，f（2，0））
        =最大值（分钟（5，40），分钟（40，5））
        =（5,1）（留下为[10 15 55]或[10 50 55]）
 

我还没有表现出对工作用f返回的对的第二个元素（0,1），因为它很难EX preSS简洁，但很明显，这将是1，因为这两种选择试过需要1删除。

I need some help in finding the general idea for an algorithm to solve the following problem. The problem has been given to me in an assignment. It looks like it should be solvable through a greedy method, but I can't figure out a simple solution. Here's the problem description:

You are given a sequence of N numbers a_1 ... a_n such that 0 = a_1 < a_2 < ... < a_n. You must eliminate at most M of these numbers such that the minimum difference a_i+1 - a_i between any two consecutive numbers is maximized.

You may not eliminate the first and last elements, a_0 and a_n. Also you must eliminate as few numbers as possible: if eliminating M - 1 you get the shortest distance to be D and eliminating M you still have the same minimum difference, you must not eliminate this last number.

I'm not asking for a complete solution to this problem. Only a few guidelines as to how the algorithm might look.

Edit: Some test samples. Keep in mind that there may be multiple valid solutions.

Remove at most 7 from:
0 3 7 10 15 18 26 31 38 44 53 60 61 73 76 80 81 88 93 100

Solution:
0 7 15 26 31 38 44 53 60 73 80 88 93 100

Remove at most 8 from:
0 3 7 10 15 26 38 44 53 61 76 80 88 93 100

Solution:
0 15 38 53 76 88 100

解决方案

[EDIT: I originally claimed that ElKamina's answer was wrong, but I've now convinced myself that not only is it correct, it's virtually the same as my (later) answer :-P Still a bit terse for my taste though!]

Here's an exact O(NM^2)-time, O(NM)-space dynamic programming algorithm that gets the right answer on all the OP's examples in milliseconds. The basic ideas are that:

Whenever we impose the constraint that a particular number should not be deleted, it forms a "fence" between two subproblems in such a way that solving each subproblem optimally guarantees an optimal solution to the overall problem with that constraint in place, and Every optimal solution must begin with a non-deleted number, followed by some number of consecutive deleted numbers, followed by a non-deleted number, followed by an optimal solution to the remainder of the problem that begins at the second non-deleted number and uses an appropriately reduced M.

In the following, x[i] means the ith number in the list, with indexing starting from 0.

The recursion

Let f(i, j) be the optimal (largest minimum) interval size obtainable from the suffix of the number list starting at position 0 <= i < N by keeping this (i.e. the ith) number and deleting exactly j of the later (not necessarily consecutive) numbers. The following recursion shows how this can be computed:

f(i, j) = max(g(i, j, d)) over all 0 <= d <= min(j, N-i-2)
g(i, j, d) = min(x[i+d+1] - x[i], f(i+d+1, j-d))

The min(j, N-i-2) is there instead of just plain j to prevent deletions "past the end". The only base cases we need are:

f(N-1, 0) = infinity (this has the effect of making min(f(N-1), 0), z) = z)
f(N-1, j > 0) = 0 (this case only arises if M > N - 2)

How it works

In more detail, to calculate f(i, j), what we do is loop over all possible numbers (including zero) of consecutive deletions starting at position i+1, in each case calculating the minimum of (a) the interval formed by this block of deletions and (b) the optimal solution to the subproblem beginning on the first undeleted number to the right of this block. It's important to specify that the first number in a block (x[i]) is not deleted, so that the previous (parent) subproblem's interval is always "capped". This is a tricky part that took me a while to figure out.

Making it fast

If you code up the plain recursion above it will work, but it will take time exponential in M and N. By memoising f(), we guarantee that its body will be run at most N * M times (once per distinct parameter combination). Each time the function runs it performs O(M) work scanning through increasingly long blocks of deletions, for O(NM^2) time overall.

You cannot create a larger gap by using fewer deletions, so the overall largest minimum interval size can be found by looking through the M+1 results f(0, M), f(0, M-1), ..., f(0, 0) for the first number that is smaller than a previous number: that previous number is the answer, and the second argument to f() is the minimum number of deletions required. To find an optimal solution (i.e. a list of the particular numbers deleted), you can record decisions made in a separate predecessor array, so that p[i, j] gives the value of d (which can be turned into the previous values of i and j) that led to the the optimal solution for f(i, j). (Perhaps "predecessor" is confusing here: it refers to the subproblems that are solved before the current subproblem, although these subproblems appear "after" (to the right of) the suffix representing the current subproblem.) These links can then be followed to recover the delete/don't-delete decisions made.

Working C++ code

http://ideone.com/PKfhDv

Addendum: Early missteps

With a tricky problem like this, it can be helpful to look at wrong approaches and see exactly where they went wrong... :-/ I thought I'd solved the problem, but I hadn't noticed the requirement to return a solution that uses as few deletions as possible, and my initial attempts to fix this didn't work.

At first I tried defining f(i, j) to be the optimal (largest minimum) interval size obtainable from the suffix of the number list starting at position 0 <= i < N by keeping this (i.e. the ith) number and deleting anywhere from 0 up to j of the later (not necessarily consecutive) numbers. But this caused a subtle problem: it's not necessarily the case that you can assemble an optimal solution to this from optimal solutions to subproblems. I initially thought this could be fixed by changing the function to return an (interval size, minimum number of deletions needed to achieve that interval size) pair instead of just an interval size, and having it break ties between actions that share the maximum minimum interval size by always choosing the action that minimises the number of deletions. But this is not true in general, because the optimal solution to the subproblem (i.e. to some suffix of the number list) will spend deletions making the minimum interval size in that region as large as possible, even if these deletions turn out to be wasted because the prefix of the full solution will force the overall minimum to be lower anyway. Here's a counterexample using an f() that returns (interval size, minimum number of deletions needed to achieve that size) pairs:

Problem: M = 1, X = [10 15 50 55].

f(2, 0) = (5, 0) (leaving [50 55])
f(1, 1) = (40, 1) (delete 50 to leave [15 55]); *locally* this appears better
          than not deleting anything, which would leave [15 50 55] and yield
          a min-gap of 5, even though the latter would be a better choice for
          the overall problem)
f(0, 1) = max(min(5, f(1, 1)), min(40, f(2, 0))
        = max(min(5, 40), min(40, 5))
        = (5, 1) (leaving either [10 15 55] or [10 50 55])

I haven't shown the working for the second element of the pair returned by f(0, 1) because it's hard to express concisely, but obviously it will be 1 because both alternatives tried need 1 deletion.