Longest Turbulent Subarray ใน C++

คำอธิบายปัญหา

Subarray ถือเป็น turbulent เมื่อเครื่องหมายเปรียบเทียบระหว่างสมาชิกติดกันสลับกันตลอด (มากกว่า/น้อยกว่าสลับกัน) ต้องการหาความยาว turbulent subarray สูงสุด

ตัวอย่าง: [9,4,2,10,7,8,8,1,9] → 5 (subarray: [4,2,10,7,8] เป็น 4>2<10>7<8)

วิธีแก้ปัญหา (DP แบบ O(1) Space)

เก็บความยาว turbulent subarray ที่ลงท้ายที่ i โดยพิจารณา 2 กรณี:

• prevBig: ความยาวที่ลงท้ายด้วย ">" (A[i-1] > A[i])
• prevSmall: ความยาวที่ลงท้ายด้วย "<" (A[i-1] < A[i])

การสลับ: ถ้า A[i] > A[i-1] → currBig = prevSmall + 1, ถ้า A[i] < A[i-1] → currSmall = prevBig + 1

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxTurbulenceSize(vector<int>& A) {
        int n = A.size();
        if(n < 2) return n;
        
        int prevBig = 1, prevSmall = 1;
        int currBig = 1, currSmall = 1;
        int ret = 1;
        
        for(int i = 1; i < n; i++) {
            if(A[i] > A[i-1]) {
                currBig = prevSmall + 1;
            } else {
                currBig = 1;
            }
            if(A[i] < A[i-1]) {
                currSmall = prevBig + 1;
            } else {
                currSmall = 1;
            }
            ret = max({ret, currBig, currSmall});
            prevBig = currBig;
            prevSmall = currSmall;
        }
        return ret;
    }
};

int main() {
    vector<int> v1 = {9,4,2,10,7,8,8,1,9};
    Solution ob;
    cout << ob.maxTurbulenceSize(v1);
    return 0;
}

อินพุต

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

เอาต์พุต

5