Giả sử chúng ta có một mảng A với n phần tử. Chúng ta có thể thực hiện các phép toán này bất kỳ số lần nào:
Chọn bất kỳ số nguyên dương k nào
Chọn bất kỳ vị trí nào trong dãy và chèn k vào vị trí đó
Vì vậy, dãy thay đổi, chúng ta tiếp tục với dãy này trong phép toán tiếp theo.
Chúng ta phải tìm số phép toán tối thiểu cần thiết để thỏa mãn điều kiện: A[i] <= i cho mọi i trong khoảng 0 đến n-1.
Ví dụ, nếu đầu vào là A = [1, 2, 5, 7, 4], thì đầu ra sẽ là 3, vì ta có thể thực hiện các phép toán như: [1,2,5,7,4] thành [1,2,3,5,7,4] thành [1,2,3,4,5,7,4] thành [1,2,3,4,5,3,7,4].
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
maxj := 0 n := kích thước của A for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), do: maxj := maximum của maxj và (A[i] - i - 1) return maxj
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#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; }Đầu vào
{ 1, 2, 5, 7, 4 }Đầu ra
3