C++ এ দীর্ঘতম অশান্ত সাবারে

A[i], A[i+1], ..., A[j]-এর একটি সাবঅ্যারে বিবেচনা করুন যখন এটি এই শর্তগুলি পূরণ করে −

• i <=k A[k+1] যখন k বিজোড় হয়, এবং A[k]

• অন্যথায়, i <=k A[k+1] যখন k জোড় হয়, এবং A[k]

সুতরাং সাব্যারে অশান্ত হয় যদি তুলনা চিহ্নটি সাব্যারেতে প্রতিটি সন্নিহিত জোড়া উপাদানের মধ্যে উল্টে যায়। এখন A-এর সর্বাধিক আকারের অশান্ত সাবয়ারের দৈর্ঘ্য খুঁজুন। সুতরাং যদি ইনপুটটি [9,4,2,10,7,8,8,1,9] এর মত হয়, আউটপুট 5 হয়। কারণ A[1]> A[2] A[4]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=অ্যারের আকার A

• prevBig :=1, prevSmall :=1, currBig :=1, currSmall :=1 এবং ret :=1

• 1 থেকে n – 1

  রেঞ্জের জন্য i

  • যদি A[i]> A[i – 1] হয়, তাহলে currBig :=1 + prevSmall

  • যদি A[i]

  • ret :=ret, currBig এবং currSmall-এর সর্বোচ্চ

  • prevSmall :=currSmall, prevBig :=currBig, currSmall :=1, currBig :=1

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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;
   }  
};
main(){
   vector<int> v1 = {9,4,2,10,7,8,8,1,9};
   Solution ob;
   cout << (ob.maxTurbulenceSize(v1));
}

ইনপুট

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

আউটপুট

5