LeetCode 376. Wiggle Subsequence

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return n;
        int up[n], down[n];
        up[0] = down[0] = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1])
                up[i] = max(up[i - 1], down[i - 1] + 1), down[i] = down[i - 1];
            else if (nums[i] < nums[i - 1])
                down[i] = max(down[i - 1], up[i - 1] + 1), up[i] = up[i - 1];
            else
                up[i] = up[i - 1], down[i] = down[i - 1];
        }
        return max(up[n - 1], down[n - 1]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size(), up = 1, down = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) up = max(up, down + 1);
            else if (nums[i] < nums[i - 1]) down = max(down, up + 1);
        }
        return max(up, down);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return n;
        int preDiff = nums[1] - nums[0],
            ans = preDiff != 0 ? 2 : 1;
        for (int i = 1; i < n; ++i) {
            int diff = nums[i] - nums[i - 1];
            if (diff > 0 && preDiff <= 0 ||
                diff < 0 && preDiff >= 0)
                ++ans, preDiff = diff;
        }
        return ans;
    }
};