我最近试图解决一个问题，该问题将 n 个排序的整数作为输入，我们必须从数组中删除 k 个整数以最大化两个连续项之间的最小差异。
示例测试用例: 数组:6,7,10,13,15 删除 2 个整数。
答案:删除的整数:7,13
我的方法:
因为我们必须删除 k 个整数，所以我们迭代数组 k 次。在每次迭代中，我们计算两个连续项之间的最小差值。 假设在一次迭代后，对 i 和 i+1 具有最小差异。然后我们比较 i-1 和 i+1 之间的差异以及 i 和 i+2 之间的差异。 如果第一个更大，那么我们删除术语 i，否则我们删除 i+1。
这种方法给我一个错误的答案。
因为对 n 和 k 的约束很低 ( 1<=k<=n<=30 )。 我相信这个问题可以使用动态规划来解决，但我不知道如何处理它。
任何帮助都会很好。我不希望代码只是算法及其派生方式。 提前致谢
最佳答案
这是一个相当简单的立方时间算法。如果我们预先确定最小差异，那么线性时间贪婪算法会告诉我们需要删除多少元素(从左到右扫描一次，仅在需要时删除过去的选择)。遍历所有 n 选择 2 = O(n^2) 可能的最小差异并取最大导致最多 k 删除。 (要达到 O(n^2 log n):对这些可能的最小值进行排序并使用二进制搜索。)
关于algorithm - 删除数组中k个元素的动态规划算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25337401/