किसी भी (सन्निकट) उपसरणी B (A की) को पर्वत कहा जाता है यदि निम्नलिखित गुण लागू होते हैं -
- B का आकार >= 3
- कुछ 0 < i < B.length - 1 मौजूद है जैसे कि B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
मान लीजिए हमारे पास पूर्णांकों की एक सरणी A है; हमें सबसे लंबे पर्वत की लंबाई ढूंढनी है। यदि कोई पर्वत नहीं है तो हमें 0 लौटाना है। तो यदि इनपुट [2,1,4,7,3,2,5] जैसा है, तो परिणाम 5 होगा। तो सबसे बड़ा पर्वत [1,4,7,3,2] होगा, जिसकी लंबाई 5 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- ret := 0, n := सरणी a का आकार
- i := 0 से n - 1 तक, i को j + 1 से बढ़ाएं
- j := i
- down := false, up := false
- जब तक j + 1 < n और a[j + 1] > a[j]
- up := true और j को 1 से बढ़ाएं
- जब तक up true है और j + 1 < n और a[j + 1] > a[j]
- down := true और j को 1 से बढ़ाएं
- यदि up और down दोनों true हैं, तो ret := j - i + 1 और ret का अधिकतम सेट करें, j को 1 से घटाएं
- ret लौटाएं।
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestMountain(vector<int>& a) {
int ret = 0;
int n = a.size();
int j;
for(int i = 0; i < n; i = j + 1){
j = i;
bool down = false;
bool up = false;
while(j + 1 < n && a[j + 1] > a[j]) {
up = true;
j++;
}
while(up && j + 1 < n && a[j + 1] < a[j]){
down = true;
j++;
}
if(up && down){
ret = max(j - i + 1, ret);
j--;
}
}
return ret;
}
};
main(){
vector<int> v = {2,1,4,7,3,2,5};
Solution ob;
cout << (ob.longestMountain(v));
}
इनपुट
[2,1,4,7,3,2,5]
आउटपुट
5
