线性动态规划：最长摆动子序列 题目描述 给定一个整数数组 nums ，返回其中最长的摆动子序列的长度。摆动子序列是指相邻元素的差在正负之间严格交替（第一个差可以是正数或负数）。仅有一个元素的序列也被视为摆动序列。如果有两个元素，它们不能相等，否则无法形成有效的摆动。 例如： 输入： nums = [1,7,4,9,2,5] ，输出：6（整个序列就是摆动序列） 输入： nums = [1,17,5,10,13,15,10,5,16,8] ，输出：7（子序列 [1,17,5,10,5,16,8] 的差为 +16, -12, +5, -5, +11, -8 ） 解题过程 1. 问题分析 摆动序列要求相邻元素的差交替变化。核心在于跟踪序列的“上升”和“下降”趋势。动态规划可以通过状态机思想处理两种状态：以当前元素结尾且呈上升趋势（即 nums[i] > nums[j] 的 j 是前一个下降趋势的结尾），或呈下降趋势。 2. 状态定义 定义两个数组： up[i] ：以第 i 个元素结尾，且最后呈上升趋势（即 nums[i] 比前一个元素大）的最长摆动子序列长度。 down[i] ：以第 i 个元素结尾，且最后呈下降趋势（即 nums[i] 比前一个元素小）的最长摆动子序列长度。 3. 状态转移方程 遍历到 nums[i] 时，比较它与前面所有 nums[j] （ j < i ）： 如果 nums[i] > nums[j] ：说明可以在 j 结尾的下降序列后接上 i ，形成上升趋势，故 up[i] = max(up[i], down[j] + 1) 。 如果 nums[i] < nums[j] ：说明可以在 j 结尾的上升序列后接上 i ，形成下降趋势，故 down[i] = max(down[i], up[j] + 1) 。 如果相等，则跳过（因为相等元素不能改变趋势）。 4. 初始化 每个元素自身至少形成长度为 1 的摆动序列，因此初始化 up[i] = 1 ， down[i] = 1 （对所有 i ）。 5. 优化转移过程 无需对每个 i 遍历所有 j < i ，可以维护到当前为止的全局最长上升/下降长度。具体： 遍历数组，比较 nums[i] 和 nums[i-1] ： 若 nums[i] > nums[i-1] ：当前上升趋势的长度 = 前一个下降趋势长度 + 1（ up = down_prev + 1 ），下降趋势长度不变。 若 nums[i] < nums[i-1] ：当前下降趋势的长度 = 前一个上升趋势长度 + 1（ down = up_prev + 1 ），上升趋势长度不变。 若相等：两个趋势长度均不变。 6. 举例说明 以 nums = [1,17,5,10,13,15,10,5,16,8] 为例： 初始化： up = down = 1 i=1: 17>1 → up=2, down=1 i=2: 5<17 → down=up_prev+1=2+1=3, up=2 （注意：此处 down=3 对应序列 [1,17,5] ） i=3: 10>5 → up=down_prev+1=3+1=4, down=3 （序列 [1,17,5,10] ） i=4: 13>10 → up=down_prev+1=3+1=4 （不变，因为 13 接在 10 后不改变上升趋势的连续性） i=5: 15>13 → 同理 up 不变 i=6: 10<15 → down=up_prev+1=4+1=5 i=7: 5<10 → down=up_prev+1=4+1=5 （不变） i=8: 16>5 → up=down_prev+1=5+1=6 i=9: 8<16 → down=up_prev+1=6+1=7 最终结果： max(up, down) = 7 。 7. 复杂度分析 时间复杂度 O(n)，空间复杂度 O(1)（仅需两个变量跟踪 up 和 down ）。 8. 核心思想 通过维护两种状态（上升/下降）的长度，避免暴力枚举所有子序列，利用摆动序列的交替特性简化动态规划。