使阵列严格增加所需的最小数量的更改

Question

我有一个问题,我们有一个正数的数组,我们必须通过对数组元素进行零或更多的更改来严格增加它.

我们被问到使阵列严格增加所需的最小更改次数.

例

如果数组是1 2 9 10 3 15

所以如果将3改为12到14之间的某个数字,则ans = 1.

如果1 2 2 2 3 4 5

ANS = 5

因为改变2到3然后是2到4然后是3到5然后是4到6然后是5到7

约束:

数组中的元素数<= 10 ^ 6

每个元素<= 10 ^ 9

注意:

这不是一个功课,在我的采访中被问到,我无法给出算法.

有人可以给我一个算法吗？

链接到示例测试用例的详细问题 https://www.hackerearth.com/problem/algorithm/find-path/

由于它是迷你/最大问题,所以它听起来像我的动态编程,但我需要帮助.

Answer 1

提示1

这非常接近标准的最长增长子序列问题,该问题可在O(nlogn)中解决.

如果您可以将数字更改为小数,那么答案将是相同的.(最小变化数量=最长增长子序列的字符串长度)

但是,由于您需要在两者之间使用不同的积分值,因此您必须稍微修改标准算法.

提示2

考虑如果通过执行x [i] = x [i] -i更改数组会发生什么.

您现在需要通过进行最小数量的更改来修改此更改的数组,以使每个元素增加或保持不变.

您现在可以在此数组中搜索最长的非递减子序列,这将告诉您有多少元素可以保持不变.

但是,这仍然可以使用负整数.

提示3

将算法修改为仅使用正数的一种简单方法是在数组的开头附加大量数字.

即将1,2,9,10,3,15改为-5,-4,-3,-2,-1,1,2,9,10,3,15

然后你可以确定最佳答案永远不会决定让1变为负数,因为将所有负数减小会花费太多.

(您还可以修改最长的增加子序列算法以获得附加约束,但在面试情况下这可能更难以正确编码.)

例1

通过最初的例子:

原始序列

1,2,9,10,3,15

在开始时添加虚拟元素

-5,-4,-3,-2,-1,1,2,9,10,3,15

减去数组中的位置

-5,-5,-5,-5,-5,-4,-4,2,2,-6,5

找到最长的非递减序列

-5,-5,-5,-5,-5,-4,-4,2,2,*,5

所以答案是改变一个数字.

例2

原始序列

1,2,2,2,3,4,5

在开始时添加虚拟元素

-5,-4,-3,-2,-1,1,2,2,2,3,4,5

减去数组中的位置

-5,-5,-5,-5,-5,-4,-4,-5,-6,-6,-6,-6

找到最长的非递减序列

-5,-5,-5,-5,-5,-4,-4,*,*,*,*,*

所以答案是改变5个数字.