我最近在一次采访中遇到了这个问题.我无法想出一个算法.
给定一个未排序的整数数组,我们必须找到将此数组转换为算术级数的最小成本,如果在数组中更改了任何元素,则会产生1个单位的成本.此外,元素的值介于(-inf,inf)之间.
我有点意识到DP可以在这里使用,但我无法解决这个问题.价值观受到一些限制,但我不记得了.我只是在寻找高级伪代码.
给定未排序整数数组a = [a_1, a_2, ..., a_n]，令diffs = [a_2-a_1, a_3-a_2, ..., a_n-a_(n-1)].
查找 中 的最大出现值diffs并根据需要调整任何值，a以使所有相邻值相差该量。