wiggle sequence

这题没有做过类似的，所以感觉还是有点难度的，先来看下题目：

A sequence of numbers is called a wiggle sequence if 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 fewer than two elements is trivially a wiggle sequence.

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

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Example 1:

Input: [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence.

Example 2:

Input: [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].

Example 3:

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

Follow up: Can you do it in O(n) time?

这题主要是算相邻两个元素的差值，看看最长的正负差值长度，通俗的来说，也就是看最长的单调变化序列长度，所以在这个序列里，总遵循着小大小大小大这样的规律。

这题一开始就觉得可以用dp，但是一个dp貌似很难去做，想了半天也没想出解法，于是换种思路来求解。

我们设置两个值，分别是目前最长的下降序列长度和上升序列长度，然后不断的两两比较相邻的两个元素的值，这两个元素假如不相等，那么必定可以组成一个单调的子序列，分别有如下两个情况：

• 上升序列。在这种情况下，上升序列必定可以使下降序列的长度增加一，当然这里理解起来有点复杂，需要分各种情况讨论：
  • 该子序列的值都比下降序列最后一个元素的值小。这种情况的话，其实还是能使得下降序列的长度增加一的，让下降序列的前一个元素指向子序列的第一个元素就可以。
  • 该子序列的值都比下降序列最后一个元素的值大，很好理解，直接下降序列长度加一。
• 下降序列，和上升序列一样。

值得注意的是，是的序列长度加一后，原先的下降序列变成了上升序列，上升序列变成了下降序列。

以下是代码实现，很简单，但是思路花费的时间还是挺长的。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        int up = 1;
        int down = 1;
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) {
                // Increase down length
                if (down + 1 > up) {
                    up = down + 1;
                }
            } else if (nums[i] < nums[i - 1]) {
                // Increase up length
                if (up + 1 > down) {
                    down = up + 1;
                }
            }
        }
        return max(down, up);
    }
};