假设我们有一个包含 n 个元素的数组 A。我们可以多次执行这些操作 -

• 选择任何正整数 k

• 选择任何位置并在该位置插入k

• 这样，序列就改变了，我们在下一个操作中继续这个序列。

ul>

我们必须找到满足条件所需的最少操作数：对于 0 到 n-1 范围内的所有 i，A[i]

因此，如果输入是比如 A = [1, 2, 5, 7, 4]，那么输出将为 3，因为我们可以执行如下操作： [1,2,5,7,4] 到 [1,2,3,5 ,7,4] 到 [1,2,3,4,5,7,4] 到 [1,2,3,4,5,3,7,4]。

步骤 h2>

为了解决这个问题，我们将按照以下步骤操作 -

maxj := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   maxj := maximum of maxj and (A[i] - i - 1)
return maxj

示例

让我们看一下以下实现以获得更好的理解 −

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
   int maxj = 0;
   int n = A.size();
   for (int i = 0; i < n; i++) {
      maxj = max(maxj, A[i] - i - 1);
   }
   return maxj;
}
int main() {
   vector<int> A = { 1, 2, 5, 7, 4 };
   cout << solve(A) << endl;
}

输入

{ 1, 2, 5, 7, 4 }

输出

3