区间动态规划例题：最长摆动子序列问题（相邻元素差正负交替） 题目描述 给定一个整数数组 nums ，找到其中最长的摆动子序列的长度。摆动子序列定义为：相邻元素的差严格正负交替（例如，[ 1, 7, 4, 9, 2, 5 ] 的相邻差为 6, -3, 5, -7, 3，正负交替）。注意：子序列不要求连续，但必须保持原始顺序。如果数组只有一个元素，则视为长度为 1 的摆动序列。 示例 输入： nums = [1, 7, 4, 9, 2, 5] 输出： 6 （整个序列就是摆动序列） 输入： nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8] 输出： 7 （子序列 [ 1, 17, 10, 13, 10, 16, 8 ] 的差为 16, -7, 3, -3, 6, -8，正负交替） 解题过程 步骤 1：理解摆动序列的性质 摆动序列的关键是相邻元素的差（ nums[i] - nums[i-1] ）必须正负交替。例如： 如果当前差为正（"上升"），则下一个差必须为负（"下降"）。 如果当前差为负（"下降"），则下一个差必须为正（"上升"）。 步骤 2：定义状态 使用区间动态规划时，我们定义两个状态数组： up[i] ：以第 i 个元素结尾的最长摆动子序列长度，且最后一步是"上升"（即 nums[i] > nums[j] ，其中 j < i ）。 down[i] ：以第 i 个元素结尾的最长摆动子序列长度，且最后一步是"下降"（即 nums[i] < nums[j] ，其中 j < i ）。 为什么这样定义？ 因为摆动序列的最后一个动作可能是上升或下降，我们需要分别记录这两种情况，以便后续扩展。 步骤 3：状态转移方程 对于每个位置 i （从 0 到 n-1），初始化 up[i] = down[i] = 1 （至少可以单独取自己）。 然后遍历 j 从 0 到 i-1 ： 如果 nums[i] > nums[j] ： 当前是上升，那么前一步必须是下降，所以 up[i] = max(up[i], down[j] + 1) 。 如果 nums[i] < nums[j] ： 当前是下降，那么前一步必须是上升，所以 down[i] = max(down[i], up[j] + 1) 。 如果相等，则跳过（差为 0 不符合摆动条件）。 步骤 4：示例推导 以 nums = [1, 7, 4, 9, 2, 5] 为例： i=0: up[ 0]=1, down[ 0 ]=1 i=1: j=0: nums[ 1]=7 > nums[ 0]=1 → up[ 1] = max(1, down[ 0 ]+1)=2 down[ 1 ] 保持 1 i=2: j=0: nums[ 2]=4 > nums[ 0]=1 → up[ 2]=max(1, down[ 0 ]+1)=2 j=1: nums[ 2]=4 < nums[ 1]=7 → down[ 2]=max(1, up[ 1 ]+1)=3 i=3: j=0: 9>1 → up[ 3]=max(1, down[ 0 ]+1)=2 j=1: 9>7 → up[ 3]=max(2, down[ 1 ]+1)=2（不变） j=2: 9>4 → up[ 3]=max(2, down[ 2 ]+1)=4 down[ 3 ] 保持 1 i=4: j=0: 2>1 → up[ 4]=max(1, down[ 0 ]+1)=2 j=1: 2<7 → down[ 4]=max(1, up[ 1 ]+1)=3 j=2: 2<4 → down[ 4]=max(3, up[ 2 ]+1)=3 j=3: 2<9 → down[ 4]=max(3, up[ 3 ]+1)=5 i=5: j=0: 5>1 → up[ 5]=max(1, down[ 0 ]+1)=2 j=1: 5<7 → down[ 5]=max(1, up[ 1 ]+1)=3 j=2: 5>4 → up[ 5]=max(2, down[ 2 ]+1)=4 j=3: 5<9 → down[ 5]=max(3, up[ 3 ]+1)=5 j=4: 5>2 → up[ 5]=max(4, down[ 4 ]+1)=6 最终结果： max(up[5], down[5]) = 6 。 步骤 5：优化 注意到每次更新只依赖于前一个状态，可以优化空间复杂度为 O(1)，但时间仍需 O(n²)。另一种贪心解法（O(n)）存在，但这里我们重点理解区间 DP 的思路。 总结 通过 up[i] 和 down[i] 分别记录以 i 结尾的上升和下降摆动序列长度，利用前驱状态递推，最终取最大值即为最长摆动子序列长度。