leetcode 376. Wiggle Subsequence

Title address (376. Swing sequence )

https://leetcode-cn.com/problems/wiggle-subsequence/

Title Description

 If the difference between consecutive numbers strictly alternates between positive and negative numbers , Then the number sequence is called the swing sequence . First difference （ If it exists ） It could be positive or negative . A sequence of less than two elements is also a wobble sequence .

 for example , [1,7,4,9,2,5]  It's a sequence of oscillations , Because of the difference  (6,-3,5,-7,3)  It's alternating positive and negative . contrary , [1,4,7,2,5]  and  [1,7,4,5,5]  It's not a wobble sequence , The first sequence is because its first two differences are positive , The second sequence is because its last difference is zero .

 Given a sequence of integers , Returns the length of the longest subsequence as a swing sequence .  By removing some... From the original sequence （ It can also be done without deleting ） Element to get the subsequence , The remaining elements keep their original order .

 Example  1:

   Input : [1,7,4,9,2,5]
   Output : 6 
   explain :  The whole sequence is a swing sequence .

 Example  2:

   Input : [1,17,5,10,13,15,10,5,16,8]
   Output : 7
   explain :  This sequence contains several lengths of  7  Swing sequence , One of them can be [1,17,10,13,10,16,8].

 Example  3:

   Input : [1,2,3,4,5,6,7,8,9]
   Output : 2

 Advanced :
   Can you use  O(n)  Time complexity to complete this question ?

Paste below leetcode The solution of the great God , In order to look back later

Paste here the explanation of a great God in the solution to the dynamic programming code .

class Solution {
    
public:
    int wiggleMaxLength(vector<int>& nums) {
    
        int i, down = 1, up = 1, len = nums.size();
        for(i=1;i<len;i++){
    
            if(nums[i]>nums[i-1]){
    
                up = down + 1;
            }
            else if(nums[i]<nums[i-1]){
    
                down = up + 1;
            }
        }
        return len == 0 ? 0 : max(up, down);
        //len == 0( Empty list []) When to return to 0,len == 1( That is, an element [3]) When to return to 1
    }
};

Paste it here leetcode Official explanation
Both ends of the sequence must be peaks or valleys , If the first two of the sequence are the same data , There is only one front end , therefore prevdiff=1, If the first two of the sequence are different data , That may be ascending or descending , Then add this situation ,prevdiff In the beginning, it was 2

// Greedy Algorithm 
class Solution {
    
public:
    int wiggleMaxLength(vector<int>& nums) {
    
        int n = nums.size();
        if (n < 2) {
    
            return n;
        }
        int prevdiff = nums[1] - nums[0];
        int ret = prevdiff != 0 ? 2 : 1;
        for (int i = 2; i < n; i++) {
    
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
    
                ret++;
                prevdiff = diff;
            }
        }
        return ret;
    }
};