Dãy con Wiggle dài nhất trong C++

Mô tả bài toán

Dãy wiggle là dãy mà hiệu giữa các phần tử liên tiếp thay đổi dấu liên tục (dương, âm, dương...). Tìm độ dài dãy con wiggle dài nhất (giữ thứ tự gốc).

Ví dụ: [1,7,4,9,2,5] → hiệu [6,-3,5,-7,3] xen kẽ dấu → độ dài 6.

Giải thuật DP O(n) 2 trạng thái

Giữ 2 biến:

• up: độ dài dãy wiggle kết thúc tại i với hiệu dương lần cuối.
• down: độ dài dãy wiggle kết thúc tại i với hiệu âm lần cuối.

• Nếu nums[i] > nums[i-1]: up = down + 1.
• Nếu nums[i] < nums[i-1]: down = up + 1.
• Nếu bằng nhau: không đổi.

Cài đặt C++

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

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) 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() {
    vector<int> v = {1,7,4,9,2,5};
    Solution ob;
    cout << ob.wiggleMaxLength(v); // 6
    return 0;
}

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(1).