A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.


	For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative.
	In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.


A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Given an integer array nums, return the length of the longest wiggle subsequence of nums.

&nbsp;
Example 1:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).


Example 2:

Input: nums = [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: There are several subsequences that achieve this length.
One is [1, 17, 10, 13, 10, 16, 8] with differences (16, -7, 3, -3, 6, -8).


Example 3:

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


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 1000
	0 &lt;= nums[i] &lt;= 1000


&nbsp;
Follow up: Could you solve this in O(n) time?

#####################################################################################################################
# Problem:  Wiggle Subsequence
# Solution : Dynamic Programming
# Time Complexity : O(n) 
# Space Complexity : O(1)
#####################################################################################################################

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        
        positive, negative = 1, 1
        
        if len(nums) < 2:
            return len(nums)
        
        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                positive = negative + 1
            elif nums[i] < nums[i - 1]:
                negative = positive + 1
                
        return max(positive, negative)
class Solution {
    int n;
    int dp[][][];
    public int wiggleMaxLength(int[] nums) {
        n = nums.length;
        dp = new int[n][1005][2];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 1005; j++){
                Arrays.fill(dp[i][j] , -1);
            }
        }
        int pos = f(0 , 0 , nums , -1);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 1005; j++){
                Arrays.fill(dp[i][j] , -1);
            }
        }
        int neg = f(0 , 1 , nums , 1001);
        return Math.max(pos , neg);
    }
    int f(int i , int posPre , int a[] , int prev){
        if(i == n) return 0;
        if(dp[i][prev + 1][posPre] != -1) return dp[i][prev + 1][posPre];
        if(posPre == 0){
            int not = f(i + 1 , 0 , a , prev);
            int take = 0;
            if(a[i] - prev > 0){
                take = f(i + 1 , 1 , a , a[i]) + 1;
            }
            return dp[i][prev + 1][posPre] = Math.max(not , take);
        }
        else{
            int not = f(i + 1 , 1 , a , prev);
            int take = 0;
            if(a[i] - prev < 0){
                take = f(i + 1 , 0 , a , a[i]) + 1;
            }
            return dp[i][prev + 1][posPre] = Math.max(not , take);
        }
    }
}
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        vector<vector<int>> dp(2, vector<int>(nums.size(),0));
        int ans = 1, high, low;
        dp[0][0] = dp[1][0] = 1;
        for(int i=1; i<nums.size(); ++i){
            high = low = 0;
            for(int j=0; j<i; ++j){
                if(nums[i]>nums[j]) low = max(low, dp[1][j]);
                else if(nums[i]<nums[j]) high = max(high, dp[0][j]);
            }
            dp[0][i] = low + 1;
            dp[1][i] = high + 1;
            ans = max({ans, dp[0][i], dp[1][i]});
        }
        return ans;
    }
};
/**
 * @param {number[]} nums
 * @return {number}
 */
var wiggleMaxLength = function(nums) {
    //two pass
    //assume we start with positive or start with negative
    //choose the longest of the two
    return Math.max(helper(nums,true),helper(nums,false))
};

const helper =  (nums, start) =>{
    let l = 0
    let r = 1
    let res = nums.length
    let sign = start
    while(r < nums.length){
        //if sign are what we expected, just flip the sign
        if((sign && nums[r] > nums[l]) || (!sign && nums[r] < nums[l])){
            sign = !sign
        }
        //if sign aren't what we expected then we "remove" one
        //if we want positive then we remove the bigger number to give us a better chance of getting positive
        //if we want negative we remove the smaller number go give us a chance of getting a negative
        // want negative but nums[r] - nums[l] = positive   => remove nums[l] 
        // want positive but nums[r] - nums[l] = negative   => remove nums[l]
        //it just so happens that the number we want to remove will always be nums[l], so we don't have to do anything special
        else{
            res--
        }
        l++
        r++
    }
    return res
}
Wiggle Subsequence