Subarray ที่ยาวที่สุดใน C++

ลองพิจารณาอาร์เรย์ย่อย A[i], A[i+1], ..., A[j] ของ A ว่าปั่นป่วนเมื่อเป็นไปตามเงื่อนไขเหล่านี้ -

• สำหรับ i <=k A[k+1] เมื่อ k เป็นเลขคี่ และ A[k]

• มิฉะนั้น สำหรับ i <=k A[k+1] เมื่อ k เป็นเลขคู่ และ A[k]

ดังนั้นอาร์เรย์ย่อยจะมีความปั่นป่วนหากเครื่องหมายเปรียบเทียบพลิกไปมาระหว่างคู่ขององค์ประกอบที่อยู่ติดกันในอาร์เรย์ย่อย ตอนนี้หาความยาวของขนาดสูงสุดของ subarray ที่ปั่นป่วนขนาดสูงสุดของ A ดังนั้นหากอินพุตเป็นเหมือน [9,4,2,10,7,8,8,1,9] เอาต์พุตคือ 5 นี่เป็นเพราะ A[1]> เอ[2] <เอ[3]> เอ[4] <เอ[5]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของอาร์เรย์ A

• prevBig :=1, prevSmall :=1, currBig :=1, currSmall :=1 และ ret :=1

• สำหรับฉันอยู่ในช่วง 1 ถึง n – 1

  • ถ้า 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