algorithm/Algorithm/cpp/0376.WiggleSubsequence/wiggleMaxLength.cpp at master · wuvei/algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() == 1) return 1;
        else if (nums.size() == 2) return (nums[0] == nums[1])? 1: 2;
        int inc = 1, dec = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1])
                inc = dec + 1;
            else if (nums[i] < nums[i - 1])
                dec = inc + 1;
        }
        return std::max(inc, dec);
    }
};

// greedy
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() < 2) return 1;
        int ans = 1, flag = 0;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] < nums[i - 1] && flag != -1) {
                ++ans;
                flag = -1;
            }
            else if (nums[i] > nums[i - 1] && flag != 1) {
                ++ans;
                flag = 1;
            }
        }
        return ans;
    }
};