A[i], A[i+1], ..., A[j] সাবঅ্যারেকে turbulent বলা হয় যদি এটি নিচের শর্তগুলো পূরণ করে -
i ≤ k < j এবং A[k] > A[k+1] যখন k বিজোড়, এবং A[k] < A[k+1] যখন k জোড়;
অন্যথায়, i ≤ k < j এবং A[k] > A[k+1] যখন k জোড়, এবং A[k] < A[k+1] যখন k বিজোড়।
অর্থাৎ সাবঅ্যারেটি turbulent হয় যদি প্রতিটি সন্নিহিত জোড়া এলিমেন্টের মধ্যে তুলনা চিহ্ন ফ্লিপ করে। A-র সর্বাধিক আকারের turbulent সাবঅ্যারের দৈর্ঘ্য খুঁজে বের করতে হবে। ইনপুট [9,4,2,10,7,8,8,1,9] হলে আউটপুট ৫। কারণ A[1] > A[2] < A[3] > A[4] < A[5]।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
n := A.size()
prevBig := 1, prevSmall := 1, currBig := 1, currSmall := 1, ret := 1
i = 1 থেকে n-1 পর্যন্ত লুপ চালান
যদি A[i] > A[i-1] হয়, currBig := 1 + prevSmall
যদি A[i] < A[i-1] হয়, currSmall := 1 + prevBig
ret := max(ret, currBig, currSmall)
prevSmall := currSmall, prevBig := currBig, currSmall := 1, currBig := 1
return ret
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#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
