सी ++ प्रोग्राम उन तत्वों को रखने के लिए आवश्यक संचालन की संख्या की गणना करने के लिए जिनकी अनुक्रमणिका मान से छोटी है

मान लीजिए कि हमारे पास n तत्वों के साथ एक सरणी A है। हम इन कार्यों को कितनी भी बार कर सकते हैं -

• कोई धनात्मक पूर्णांक k चुनें

• क्रम में किसी भी स्थिति का चयन करें और उस स्थिति में k डालें

• तो, क्रम बदल गया है, हम अगले ऑपरेशन में इस क्रम के साथ आगे बढ़ते हैं।

हमें शर्त को पूरा करने के लिए आवश्यक न्यूनतम संक्रियाओं की संख्या ज्ञात करनी होगी:A[i] <=i सभी के लिए i जो 0 से n-1 की सीमा में है।

इसलिए, यदि इनपुट ए =[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