376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。微软面试

例如， [1, 7, 4, 9, 2, 5] 是一个摆动序列，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为摆动序列的最长子序列的长度。

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

//最优，贪心算法，局部最优=整体最优，=>类似于函数的极大值
//时间On，空间O1
func wiggleMaxLength(nums []int) int {
    n := len(nums)
    if n <= 1 {
        return n
    }
    res := 1
    preDiff := 0
    for i := 1; i < n; i++ {
        curDiff := nums[i] - nums[i-1]
        if curDiff > 0 && preDiff <= 0 || curDiff < 0 && preDiff >= 0 {
            res++
            preDiff = curDiff
        }
    }
    return res
}

动规解题思路

题目只需要求长度，并不关心具体的子序列，所以可以定义max[i]为以nums[i]结尾的最长子序列长度，direction[i]为以nums[i]结尾的最长子序列的方向(-1:递减，1:递增，0:平)
如果nums[i]>nums[i-1]
1. 若direction[i-1]为1，意味着nums[i-1]结尾的最长子序列末尾选择nums[i]也是一样的，所以max[i]=max[i-1]
2. 若direction[i-1]为-1，意味着nums[i-1]结尾的最长子序列加上nums[i]可以构成更长的子序列，所以max[i]=max[i-1]+1
如果nums[i]<nums[i-1]
1. 若direction[i-1]为1，意味着nums[i-1]结尾的最长子序列末尾加上nums[i]可以构成更长的子序列，所以max[i]=max[i-1]+1
2. 若direction[i-1]为-1，意味着nums[i-1]结尾的最长子序列末尾选择nums[i]也是一样的，所以max[i]=max[i-1]
如果nums[i]=nums[i-1], 则前面最长子序列的末尾选择nums[i]与nums[i-1]是相同的，所以max[i]=max[i-1]，direction[i]=direction[i-1]
由于max[i]和direction[i]只与i-1的相关，可以只用一个变量保存即可

时间复杂度O(n)，空间复杂度O(1)

//动规 dir标记方向，滚动数组优化空间
func wiggleMaxLength(nums []int) int {
 if len(nums) < 2 {
     return len(nums)
 }
 dpMax := 1
 lastDirection := 0
 for i := 1; i < len(nums); i++ {
     if nums[i] > nums[i-1] {
         if lastDirection <= 0 {
             dpMax++
         }
         lastDirection = 1
     } else if nums[i] < nums[i-1] {
         if lastDirection >= 0 {
             dpMax++
         }
         lastDirection = -1
     }
 }
 return dpMax
}