C++ में लॉन्गेस्ट टर्ब्युलेंट सबएरे (Longest Turbulent Subarray)

एक उपसरणी A[i], A[i+1], ..., A[j] को टर्ब्युलेंट (turbulent) कहा जाता है जब यह इन शर्तों को पूरा करती है:

• i ≤ k < j के लिए, जब k विषम हो तो A[k] > A[k+1], और जब k सम हो तो A[k] < A[k+1];

• अन्यथा, i ≤ k < j के लिए, जब k सम हो तो A[k] > A[k+1], और जब k विषम हो तो A[k] < A[k+1]।

इसलिए उपसरणी टर्ब्युलेंट होती है यदि उपसरणी में प्रत्येक आसन्न जोड़ी के बीच तुलना चिन्ह बदलता रहता है। अब A के अधिकतम आकार की टर्ब्युलेंट उपसरणी की लंबाई खोजें।

उदाहरण के लिए, यदि इनपुट [9,4,2,10,7,8,8,1,9] है, तो आउटपुट 5 होगा। क्योंकि A[1] > A[2] < A[3] > A[4] < A[5]।

समाधान दृष्टिकोण

1. n := A का आकार, prevBig := 1, prevSmall := 1, currBig := 1, currSmall := 1, ret := 1

2. i को 1 से n-1 तक लूप चलाएं

3. यदि A[i] > A[i-1] तो currBig := 1 + prevSmall

4. यदि A[i] < A[i-1] तो currSmall := 1 + prevBig

5. ret := max(ret, currBig, currSmall) अपडेट करें

6. prevSmall := currSmall, prevBig := currBig, currSmall := 1, currBig := 1 रीसेट करें

7. ret लौटाएं

C++ कार्यान्वयन

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int maxTurbulenceSize(vector<int>& A) { 
        int n = A.size(); 
        int prevBig = 1; 
        int prevSmall = 1; 
        int currBig = 1; 
        int currSmall = 1; 
        int ret = 1; 
        for(int i = 1; i < n; i++){ 
            if(A[i] > A[i - 1]){ 
                currBig = 1 + prevSmall; 
            } 
            if(A[i] < A[i - 1]){ 
                currSmall = 1 + prevBig; 
            } 
            ret = max({ret, currBig, currSmall}); 
            prevSmall = currSmall; 
            prevBig = currBig; 
            currSmall = 1; 
            currBig = 1; 
        } 
        return ret; 
    } 
}; 

int main(){ 
    vector<int> v1 = {9,4,2,10,7,8,8,1,9}; 
    Solution ob; 
    cout << (ob.maxTurbulenceSize(v1)); 
    return 0; 
}

इनपुट

[9,4,2,10,7,8,8,1,9]

आउटपुट

5