मान लीजिए हमारे पास n तत्वों वाला एक सरणी A है। हम ये संक्रियाएं कितनी भी बार कर सकते हैं:
कोई भी धनात्मक पूर्णांक k चुनें
अनुक्रम में कोई भी स्थिति चुनें और उस स्थिति में k डालें
तो अनुक्रम बदल जाता है, हम अगली संक्रिया में इस अनुक्रम के साथ आगे बढ़ते हैं।
हमें शर्त को पूरा करने के लिए आवश्यक न्यूनतम संक्रियाओं की संख्या ढूंढनी है: सभी i के लिए 0 से n-1 की रेंज में A[i] <= 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