摆动序列

把每个子序列都挑出来、逐一检查是不是一上一下交替，一共 2ⁿ 个，指数级。其实根本不用枚举——最长摆动子序列的长度，等于原序列里方向转折的次数 + 1，一遍扫描数转折就行。

关键招：up = 目前以「上升」结尾的最长摆动长度，down = 以「下降」结尾的。遇上升 up = down + 1(接在一段下降之后)，遇下降 down = up + 1，相等则都不变。答案取两者最大。为什么对：每次真正改方向才接上一节，同方向连走不算新转折，所以同方向时长度不增长。

起点：从第一个数开始，up 和 down 都是 1：单独一个元素本身就是长度 1 的摆动序列。

i=1 · 7 大于 1 上升：7 比前一个 1 大，是上升。up 接在「下降段 down」后面：up = down + 1 = 2。down 不变。

i=2 · 4 小于 7 下降：4 比 7 小，是下降——方向转折了。down 接在刚才的 up 后面：down = up + 1 = 3。

i=3 · 9 大于 4 上升：9 比 4 大，又转回上升。up = down + 1 = 4。

i=4 · 2 小于 9 下降：2 比 9 小，再次转折成下降。down = up + 1 = 5。

i=5 · 5 大于 2 上升：5 比 2 大，又转上升。up = down + 1 = 6。每一步都在转折，长度一路往上涨。

答案：整段每一步都在转折，up 涨到 6、down 涨到 5。答案取两者最大 = 6，正好是全长。

负例 · 换成 [1,3,5,4,2,6]：负例分支：换个数组，开头 1→3→5 连续两次上升、没转折。i=2 时 5 大于 3 仍是升，up = down + 1 算出来还是 2，长度原地不动——同方向连走不增长，这正是「只在转折时 +1」的体现。

最长摆动子序列的长度 = 方向转折点个数 + 1。把「当前方向」当状态来维护，这是贪心 / 状态机的常见套路。