我需要一些帮助来找到算法的一般想法来解决以下问题.在任务中给了我这个问题.看起来它应该可以通过贪婪的方法解决,但我无法找到一个简单的解决方案.这是问题描述:
现在给你的序列ñ号a_1 ... a_n这样0 = a_1 < a_2 < ... < a_n.您必须消除这些数字中的至多 M个,以使a_i+1 - a_i任何两个连续数字之间的最小差异 最大化.
你可能不会消除第一个和最后一个元素,a_0和a_n.此外,你必须消除尽可能少的数字:如果消除M - 1你得到最短的距离D并消除M你仍然有相同的最小差异,你不能消除这最后一个数字.
我不是要求这个问题的完整解决方案.关于算法的外观,只有一些指导.
编辑:一些测试样本.请记住,可能有多个有效的解决方案.
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 …