मान लीजिए हमारे पास n तत्वों वाली एक सरणी A है। इस सरणी का कुछ तत्व A[i] लोकल मिनिमम कहलाता है यदि और केवल यदि यह अपने दोनों पड़ोसियों से सख्ती से कम है। इसके अलावा यदि यह अपने पड़ोसियों से सख्ती से अधिक है तो यह लोकल मैक्सिमम होगा। A[0] और A[n-1] के लिए चूंकि केवल एक पड़ोसी है, वे मैक्सिमा या मिनिमा नहीं हैं। हमें दी गई सरणी में लोकल एक्सट्रीमा की संख्या ज्ञात करनी है।
इसलिए, यदि इनपुट A = [1, 5, 2, 5] है, तो आउटपुट 2 होगा, क्योंकि A[1] पर 5 लोकल मैक्सिमा है और A[2] पर 2 लोकल मिनिमा है।
चरण
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
sum := 0 n := size of A for initialize i := 1, when i < n - 1, update (increase i by 1), do: if (A[i] < A[i - 1] and A[i] < A[i + 1]) or (A[i] > A[i + 1] and A[i] > A[i - 1]), then: (increase sum by 1) return sum
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int solve(vector<int> A){ int sum = 0; int n = A.size(); for (int i = 1; i < n - 1; i++) if ((A[i] < A[i - 1] && A[i] < A[i + 1]) || (A[i] > A[i + 1] && A[i] > A[i - 1])) sum++; return sum; } int main(){ vector<int> A = { 1, 5, 2, 5 }; cout << solve(A) << endl; }इनपुट
{ 1, 5, 2, 5 }आउटपुट
2