C++에서 가장 긴 난류 하위 배열

<시간/>

A의 부분배열 A[i], A[i+1], ..., A[j]가 다음 조건을 충족할 때 난류라고 합니다. -

k가 홀수일 때 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]