使数组严格递增所需的最少更改

我遇到一个问题，我们有一个正数数组，我们必须通过对数组元素进行零次或多次更改来使其严格增加。

我们被问到使数组严格递增所需的最少更改次数。

Example

如果数组是 1 2 9 10 3 15

因此，如果将 3 更改为 12 到 14 之间的某个数字，则 and=1。

如果 1 2 2 2 3 4 5

ans=5

因为将2更改为3，然后将2更改为4，然后将3更改为5，然后将4更改为6，然后将5更改为7

限制条件：

数组中的元素数量

每个元素

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

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

由于这是最小/最大问题，所以对我来说听起来像是动态规划，但我不确定。

HINT 1

这非常接近标准最长递增子序列问题这可以在 O(nlogn) 中解决。

如果您可以将数字更改为小数，那么答案将是相同的。 （最小变化次数=字符串长度-最长递增子序列的长度）

但是，由于您需要介于两者之间的不同积分值，因此您必须稍微修改标准算法。

HINT 2

考虑一下如果通过 x[i]=x[i]-i 更改数组会发生什么。

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

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

然而，这仍然可以使用负整数。

HINT 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个数字。