Easy to understand C++


  • 0
    G

    Two types of wiggle sub-sequences, 1. start with negative difference, 2 start with positive difference. We can know if the sub-sequence can be extended through whether the length of sub sequence is odd or even, and the difference between num[i] and num[i-1] is negative or positive.

    DP1, DP2 store the longest wiggle sub-sequence, start with negative/positive difference.

    class Solution {
    public:
        int wiggleMaxLength(vector<int>& nums) {
            if(nums.size() <= 1) return nums.size();
            int dp1 = 1, dp2 = 1;
            for(int i = 1;i < nums.size();i ++){
                if(nums[i] < nums[i-1]){
                    if(dp1%2 == 1) dp1 ++;
                    if(dp2%2 == 0) dp2 ++;
                }else if(nums[i] > nums[i-1]){
                    if(dp1%2 == 0) dp1 ++;
                    if(dp2%2 == 1) dp2 ++;
                }
            }
            return std::max(dp1, dp2);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.