> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/02-18-2022-376.md).

# 02/18/2022 376

Method:

In order to find a wiggle subsequence, we need to find a low high low high... or a high low high low pattern.  so when iterate the array, we keep the pre difference and curr difference, if curr > 0 && pre <= 0 or if curr < 0 or  pre >= 0, we increase the count value and also update the pre value.

Time O(n)

Space O(1)

```
    public class Solution {
	public int wiggleMaxLength(int[] nums) {
		if (nums.length == 0 || nums.length == 1) {
			return nums.length;
		}
		int k = 0;
		while (k < nums.length - 1 && nums[k] == nums[k + 1]) {  //Skips all the same numbers from series beginning eg 5, 5, 5, 1
			k++;
		}
		if (k == nums.length - 1) {
			return 1;
		}
		int result = 2;     // This will track the result of result array
		boolean smallReq = nums[k] < nums[k + 1];       //To check series starting pattern
		for (int i = k + 1; i < nums.length - 1; i++) {
			if (smallReq && nums[i + 1] < nums[i]) {
				nums[result] = nums[i + 1];
				result++;
				smallReq = !smallReq;    //Toggle the requirement from small to big number
			} else {
				if (!smallReq && nums[i + 1] > nums[i]) {
					nums[result] = nums[i + 1];
					result++;
					smallReq = !smallReq;    //Toggle the requirement from big to small number
				}
			}
		}
		return result;
	}
}
```

```
 if(nums.length <= 1)
            return nums.length;
        int k = 1;
        while(k<nums.length && nums[k] == nums[k-1]) k++;
        if(k == nums.length)
            return 1;
        int maxLen = 2;
        boolean isIncreasing = nums[k] > nums[k-1];
        for(int i=k+1; i<nums.length; i++) {
            if(isIncreasing && nums[i] < nums[i-1]) {
                maxLen++;
                isIncreasing = false;
            } else if(!isIncreasing && nums[i] > nums[i-1]) {
                maxLen++;
                isIncreasing = true;
            }
        }
        
        return maxLen;
```

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

We can get the wiggle subsequence array

```
public class Solution {
    
    public int wiggleMaxLength(int[] nums) {
        
		if(nums.length<=1)
			return nums.length;
		
		int k=0;
		while(k<nums.length-1 && nums[k]==nums[k+1]) k++;
		if(nums.length-1==k) return 1;
		
		nums[0] = nums[k];
		nums[1] = nums[k+1];
		
		boolean small = nums[k]>nums[k+1];
		int count = 1;
		for(int i=k+1; i<nums.length; i++){
			
			if(small && nums[count]>nums[i]){
				nums[count] = nums[i];
			}
			else if(small && nums[count]<nums[i]){
				nums[++count] = nums[i];
				small = !small;
			}
			else if(!small && nums[count]<nums[i]){
				nums[count] = nums[i];
			}
			else if(!small && nums[count]>nums[i]){
				nums[++count] = nums[i];
				small = !small;	
			}
		}
		
		return count+1;
    }

}
```

```
class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2) 
            return nums.length;
        int count = 1;
        int prev = 0;
        for (int i = 1; i < nums.length; i++) {
            int diff = nums[i] - nums[i-1]; 
            if (diff != 0 && diff * prev <= 0) {
                count++;
                prev = diff;
            }
        }
        return count;
    }
}
```