假设我们有一个包含 n 个元素的数组 A。我们可以多次执行这些操作 -
选择任何正整数 k
选择任何位置并在该位置插入k
-
这样，序列就改变了，我们在下一个操作中继续这个序列。
立即学习“C++免费学习笔记（深入）”；
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
示例
让我们看一下以下实现以获得更好的理解 −
#includeusing namespace std; int solve(vector 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 A = { 1, 2, 5, 7, 4 }; cout << solve(A) << endl; }
输入
{ 1, 2, 5, 7, 4 }输出
3
