ลำดับย่อยแบบ Wiggle ใน C++

ลำดับ Wiggle = ความต่างระหว่างตัวติดกัน สลับเครื่องหมาย + และ - (อาจเริ่ม + หรือ - ก็ได้) ลำดับน้อยกว่า 2 ตัวเป็น wiggle อัตโนมัติ หาความยาวลำดับย่อย (subsequence) วิกเกิลที่ยาวที่สุด

ตัวอย่าง: [1,7,4,9,2,5] → 6 (ทั้งลำดับเป็น wiggle: diff = 6,-3,5,-7,3)

ขั้นตอนการแก้ปัญหา (Greedy / DP O(N))

1. n = nums.size(), ถ้า n=0 คืน 0
2. up = 1, down = 1 (ความยาว wiggle ที่ลงท้ายด้วยความต่าง + และ -)
3. วน i = 1..n-1:
   • ถ้า nums[i] > nums[i-1] → up = down + 1
   • ถ้า → down = up + 1
   • (ถ้าเท่ากัน ไม่เปลี่ยนอะไร)
4. คืน max(up, down)

เหตุผล: ต้องการสลับเครื่องหมาย ดังนั้นถ้าตอนนี้ขึ้น (+) ตัวก่อนต้องลง (-) → up = down + 1

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

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

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (!n) return 0;
        int up = 1, down = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i-1]) up = down + 1;
            else if (nums[i] < nums[i-1]) down = up + 1;
        }
        return max(up, down);
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,7,4,9,2,5};
    cout << ob.wiggleMaxLength(v);
}

Input

[1,7,4,9,2,5]

Output

6