###### tags: `Leetcode` `medium` `greedy` `python`

# 376. Wiggle Subsequence

## [題目來源:]
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.

**Follow up: Could you solve this in O(n) time?**


#### [圖片來源:] https://leetcode.com/problems/wiggle-subsequence/

## 解題思路:
此題為要求數組(不用連續)任兩數隻差值為正負交替，差值若為0則亦屬不符

* ex1: nums=[1,7,4,9,2,5]
diff= [6,-3,5,-7,3] 皆為正負交替
* ex2: nums=[**1**,**17**,5,**10**,**13**,15,**10**,5,**16**,**8**]
可取[1,17,10,13,10,16,8]為wiggle subsequence

策略: 使用**greedy**
* 先求當前數 **nums[i]** 與前面數 **nums[i-1]** 的差diff
* 若diff與先前紀錄的差pre_diff正負相反，表示可以加入結果
* ex: [1,17,5,10,13,15,10,5,16,8]
* diff:[**16**,**-12**,**5**,3,2,**-5**,-5,**11**,**-8**]
* 只需看正負即可，因為題目求個數，所以不用太嚴謹:
* 對於連續正負相同的，diff應該求最min or max
* ex: 5,10,13,15 都為正，diff應該求(5,15)= 10較為嚴謹

## Python:

class Solution(object):
    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums)<2:
            return len(nums)
        pre_diff=nums[1]-nums[0]
        ##若pre_diff為0表示兩數相同 res從1開始
        res=1 if pre_diff==0 else 2
        for pos in range(2,len(nums)):
            diff=nums[pos]-nums[pos-1]
            #判斷與pre_diff的正負是否相反
            if (diff>0 and pre_diff<=0) or (diff<0 and pre_diff>=0):
                res+=1
                pre_diff=diff
        return res

result=Solution()
ans=result.wiggleMaxLength(nums = [1,17,5,10,13,15,10,5,16,8])
print(ans)