最长摆动子序列的变种：最多允许一次符号翻转的最长摆动子序列
题目描述
给定一个整数数组 nums，一个摆动子序列是指：相邻元素的差值（后一个减前一个）严格交替为正、负（或负、正）。例如，[1, 7, 4, 9, 2, 5] 是一个摆动序列，因为差值 (6, -3, 5, -7, 3) 交替为正负。但是，本题允许在最多一次相邻差值不满足交替规律的情况下（即允许一次“符号翻转”），仍然将其视为有效的摆动子序列。要求计算在最多允许一次符号翻转的条件下，nums 的最长摆动子序列的长度。
例如：nums = [1, 7, 4, 5, 5, 6, 7, 3, 9]
标准摆动子序列（不允许翻转）：[1, 7, 4, 5, 3, 9]，差值序列为 +6, -3, +1, -2, +6，长度为 6。
允许一次符号翻转：[1, 7, 4, 5, 6, 3, 9]，差值序列为 +6, -3, +1, +1, -3, +6，其中 +1, +1 连续两个正差值，这相当于允许一次符号翻转（原本应为正负交替，但这里连续两个正差值，相当于“翻转”了一次符号变化规则），长度为 7。
你的任务是找到这个最大长度。
注意：子序列不要求连续，但必须保持原始顺序。一次“符号翻转”定义为：在差值序列中，允许有一次相邻的两个差值符号相同（或其中一个为零），而其他相邻差值必须严格交替。
解题思路
本题是标准“最长摆动子序列”的扩展。标准解法用两个状态：up[i] 表示以第 i 个元素结尾、且最后一个差值为正的最长摆动子序列长度；down[i] 表示以第 i 个元素结尾、且最后一个差值为负的最长摆动子序列长度。
扩展为允许一次翻转，我们可以增加维度来表示是否已经使用过这次翻转机会。
状态定义
设 dp[i][s][f] 表示考虑前 i 个元素，以第 i 个元素结尾，且当前最后一个差值符号为 s，是否使用过翻转机会（f = 0 表示未使用，f = 1 表示已使用）的最长摆动子序列长度。
- 索引 i 从 0 到 n-1。
- 符号 s：1 表示最后一个差值为正（即 nums[i] 比前一个元素大），-1 表示最后一个差值为负（即 nums[i] 比前一个元素小），0 表示单独一个元素（没有差值，即子序列只有一个元素）。
- 实际处理时，可以简化 s 为两个状态：
up和down，然后对每个状态再区分 f。
更清晰的解法
我们用四个数组：
up0[i]：以 nums[i] 结尾，最后一步是上升（即 nums[i] > 前一个元素），且从未使用过翻转的最大长度。down0[i]：以 nums[i] 结尾，最后一步是下降（即 nums[i] < 前一个元素），且从未使用过翻转的最大长度。up1[i]：以 nums[i] 结尾，最后一步是上升，且已经使用过一次翻转的最大长度。down1[i]：以 nums[i] 结尾，最后一步是下降，且已经使用过一次翻转的最大长度。
初始条件：每个元素自身可以作为一个长度为 1 的子序列，没有差值，所以我们可以初始化 up0[i] = down0[i] = 1，up1[i] = down1[i] = 1（但注意，单独一个元素时未使用翻转，所以 up1/down1 其实在单元素时不会用到翻转，但为了统一，我们可以从 1 开始，在转移时考虑翻转）。
转移方程
对于每个 i，我们枚举所有 j < i，考虑是否将 nums[i] 接在以 nums[j] 结尾的某个子序列后面。
定义 diff = nums[i] - nums[j]。
情况 1：diff > 0（当前步是上升）
- 如果之前最后一步是下降（down0[j]），那么接上去形成正常交替，且未使用翻转：
up0[i] = max(up0[i], down0[j] + 1) - 如果之前最后一步是上升（up0[j]），但我们要接一个上升，这就违反了交替规则，此时可以使用一次翻转（如果之前未使用过翻转），即从未使用翻转的上升状态，接一个上升，变成已使用翻转的上升状态：
up1[i] = max(up1[i], up0[j] + 1) - 如果之前已经使用过翻转，且最后一步是下降（down1[j]），接一个上升，仍然保持交替（正常交替）：
up1[i] = max(up1[i], down1[j] + 1) - 如果之前已经使用过翻转，且最后一步是上升（up1[j]），再接一个上升，则连续两个上升，这不被允许（因为只能用一次翻转，已经用过了），所以不能转移。
情况 2：diff < 0（当前步是下降）
- 正常交替，从未使用翻转的上升接下降：
down0[i] = max(down0[i], up0[j] + 1) - 违反交替，从未使用翻转的下降接下降（使用翻转机会）：
down1[i] = max(down1[i], down0[j] + 1) - 已使用翻转的正常交替：从已使用翻转的上升接下降：
down1[i] = max(down1[i], up1[j] + 1) - 已使用翻转后不能再违反交替，所以已使用翻转的下降接下降不允许。
情况 3：diff == 0
差值 0 不能形成有效摆动（因为需要严格交替的正负，0 既不正也不负），所以 diff=0 时，nums[i] 不能接在 nums[j] 后面形成摆动。但 nums[i] 自身可以作为子序列起点（长度 1），这已经在初始化中体现了。
初始化
对所有 i，up0[i] = down0[i] = up1[i] = down1[i] = 1，因为至少可以取单独一个元素作为子序列。
最终答案
所有 i 的所有四个状态的最大值。
复杂度
直接按上述方法，需要 O(n²) 时间（i 和 j 两层循环）。空间 O(n) 可以只保留当前四个值，但需要记录所有 i 的状态以便 j 遍历，所以通常用数组保存所有 i 的状态，空间 O(n)。
逐步计算示例
以 nums = [1, 7, 4, 5, 5, 6, 7, 3, 9] 为例，n=9。
初始化：
up0 = [1,1,1,1,1,1,1,1,1]
down0 = [1,1,1,1,1,1,1,1,1]
up1 = [1,1,1,1,1,1,1,1,1]
down1 = [1,1,1,1,1,1,1,1,1]
i=0：只有自己，所有状态为 1。
i=1：nums[1]=7，j=0，diff=6>0。
- 从 down0[0]=1 接，正常交替：
up0[1] = max(1, 1+1)=2。 - 从 up0[0]=1 接，违反交替，使用翻转：
up1[1] = max(1, 1+1)=2。
所以 up0[1]=2, up1[1]=2，down0[1]=1, down1[1]=1。
i=2：nums[2]=4，diff(4,1)=-3<0，diff(4,7)=-3<0。
- 对 j=0：diff<0，从 up0[0]=1 接：
down0[2]=max(1,2)=2。从 down0[0]=1 接（违反交替）：down1[2]=max(1,2)=2。 - 对 j=1：diff<0，从 up0[1]=2 接：
down0[2]=max(2,3)=3。从 down0[1]=1 接（违反交替）：down1[2]=max(2,2)=2。从 up1[1]=2 接（已用翻转的正常交替）：down1[2]=max(2,3)=3。
此时 down0[2]=3, down1[2]=3, up0[2]=1, up1[2]=1。
继续计算到 i=8，最终找到最大值 7。
优化
上述 O(n²) 方法在 n 很大时较慢。我们可以优化到 O(n)：
注意到，我们只关心以每个元素结尾的四个状态，而转移时只需要考虑 nums[i] 与 nums[j] 的大小关系，其实可以维护“当前遇到的最优值”而不必枚举 j。
但允许一次翻转时，状态转移有依赖，不能像标准摆动序列那样简单 O(n)。不过可以通过记录“上一次”的值来优化。
但为简单起见，竞赛中 n ≤ 1000 时 O(n²) 足够。若 n 很大，可进一步用线段树等数据结构优化，但题目一般不会太大。
最终答案
遍历完成后，取所有 up0[i], down0[i], up1[i], down1[i] 的最大值。
关键点总结
- 状态设计：区分最后一步方向（上升/下降）和是否用过翻转。
- 转移分三类：正常交替（不消耗翻转）、消耗翻转（从同方向转移）、已用翻转后的正常交替。
- 差值 0 不能形成有效摆动步。
- 初始化长度为 1。
- 最终取所有状态最大值。