# 376. Wiggle Subsequence



```java
class Solution {
    public int wiggleMaxLength(int[] nums) {
        // caches the size of the largest wiggle subsequence
        int[] memo= new int[nums.length];
        // caches if the last diff at index is positive or negative;
        int[] sign = new int[nums.length];
        int ans = 0;
        for (int i=0; i<nums.length; i++){
            memo[i]=1;
            for (int j=0; j<i; j++){
              if(memo[j]==1 && memo[j]+1>memo[i] && nums[i]!=nums[j]){
                  memo[i]=2;
                  sign[i]= nums[i]>nums[j]? 1 : -1;
              }else if (memo[j]>1 && (nums[i]-nums[j])*sign[j]<0 && memo[j]+1 >memo[i]){
                  memo[i]=memo[j]+1;
                  sign[i] = nums[i]>nums[j]? 1 : -1;
              }
            }
            ans=Math.max(ans, memo[i]);
        }
        return ans;
    }
}
```

```java
class Solution {
    public int wiggleMaxLength(int[] nums) {
        //greedy
        
        // preDiff set to -1, 0, and 1 if nums[i]>nums[i-1], i==0, or<, respectively;
        int preDiff = 0;
        int local = nums[0];
        int ans = 1;
        for(int i=1; i<nums.length;i++){
           if(preDiff == 0 && nums[i]!=local){
               ans++;
               preDiff=nums[i]>local ? 1: -1;
               local=nums[i];
           }else if((preDiff>0 && nums[i]>local) || (preDiff<0 && nums[i]<local)){
               local=nums[i];
           }else if ((preDiff>0 && nums[i]<local) || (preDiff<0 && nums[i]>local)){
               local=nums[i];
               ans++;
               preDiff*=-1;
           }
        }
        
        return ans;
    }
}
```
