ধরুন আমাদের n উপাদান সহ একটি অ্যারে A আছে। আমরা এই অপারেশনগুলি যেকোন সংখ্যক বার করতে পারি −
-
যেকোনো ধনাত্মক পূর্ণসংখ্যা k
নির্বাচন করুন -
ক্রমানুসারে যেকোনো অবস্থান নির্বাচন করুন এবং সেই অবস্থানে k সন্নিবেশ করুন
-
সুতরাং, ক্রম পরিবর্তন করা হয়েছে, আমরা পরবর্তী অপারেশনে এই ক্রমটি নিয়ে এগিয়ে যাব।
শর্তটি পূরণ করার জন্য আমাদের প্রয়োজনীয় ন্যূনতম সংখ্যক অপারেশন খুঁজে বের করতে হবে:A[i] <=i 0 থেকে n-1 রেঞ্জের সকল 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]।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
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
