C ++中最长的湍流子数组

考虑A的子数组A [i]，A [i + 1]，...，A [j]在满足以下条件时被称为湍流-

• 当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]

为了解决这个问题，我们将遵循以下步骤-

• 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] <A [i – 1]，则currSmall：= 1 + prevBig

• ret：= ret，currBig和currSmall的最大值

• prevSmall：= currSmall，prevBig：= currBig，currSmall：= 1，currBig：= 1

• 返回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