题目描述
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1：
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2：
输入：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) 。
示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/wiggle-subsequence
算法及其思路
如果序列个数小于2，直接为摇摆数列
如果序列个数大于2，我们选择状态机的思路。
状态转换图
nums[i-1]是前一个元素，同时也是摇摆数列的最后一个元素。
nums[i]是正在扫描的元素。
判断nums[i-1]和nums[i]的关系即为当前状态。
（贪心思想）
如果序列中有递增或递减的子序列，那么一定是选择递增或递减的子序列的初值和末值。因为要尽可能地使子序列最长，那么在递增序列中的值越大（最后一个值），它后面的值的选择就可以更多。递减子序列同理。
所以状态每次转换，最长子序列的长度+1。
代码+解析
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
class Solution {
public:
int WiggleMaxLength(vector<int> nums)
{
// 序列个数小于2，直接为摇摆数列
if (nums.size() < 2)
{
return nums.size();
}
// 状态机
// 扫描序列的三种状态
// 起始态
static const int BEGIN = 0;
// 上升态
static const int UP = 1;
// 下降态
static const int DOWN = 2;
// 状态
int STATE = BEGIN;
// 序列个数小于2，直接为摇摆数列。
//所以最大长度一定大于1.
int max_len = 1;
// 从第二个元素开始扫描
for (int i = 1; i < nums.size(); i++)
{
switch (STATE)
{
case BEGIN:
if (nums[i] > nums[i - 1])
{
// 当前上升，进入上升态
STATE = UP;
max_len++;
}
else if (nums[i] < nums[i - 1])
{
// 当前下降，进入下降态
STATE = DOWN;
max_len++;
}
break;
case UP:
if (nums[i] < nums[i - 1])
{
// 上升态结束时，末值最大。
// 此时进入下降态。
STATE = DOWN;
max_len++;
}
break;
case DOWN:
if (nums[i] > nums[i - 1])
{
// 同理上升态
STATE = UP;
max_len++;
}
break;
}
}
return max_len;
}
};
void main()
{
Solution s;
int arr[10] = { 1,17,5,10,13,15,10,5,16,8 };
vector<int> numv(arr, arr + 10);
cout << "可以形成摇摆数列的最长子序列长为：" <<
s.WiggleMaxLength(numv) << endl;
}