Longest Turbulent Subarray trong C++

Mảng con A[i..j] gọi là turbulent nếu dấu so sánh đảo chiều giữa các cặp liền kề: A[k] > A[k+1] khi k lẻ và A[k] < A[k+1] khi k chẵn, HOẶC ngược lại. Tìm độ dài mảng con turbulent lớn nhất.

Ví dụ: [9,4,2,10,7,8,8,1,9] → 5 (A[1]>A[2]A[4]

Giải pháp O(n):

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

• Với i từ 1 đến n-1:
  Nếu A[i] > A[i-1]: currBig = 1 + prevSmall
  Nếu A[i] < A[i-1]: currSmall = 1 + prevBig
  ret = max(ret, currBig, currSmall)
  prevSmall=currSmall, prevBig=currBig, currSmall=1, currBig=1

• Trả về ret

Ví dụ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int maxTurbulenceSize(vector<int>& A) {       int n = A.size();       int prevBig = 1, prevSmall = 1, currBig = 1, currSmall = 1, 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;    } }; int main(){    vector<int> v1 = {9,4,2,10,7,8,8,1,9};    Solution ob;    cout << (ob.maxTurbulenceSize(v1)); }

Đầu vào

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

Đầu ra

5