区间动态规划例题：最长摆动子序列问题
字数 1245 2025-10-31 22:46:15
区间动态规划例题：最长摆动子序列问题
题目描述：
给定一个整数数组 nums，找出其中最长的摆动子序列的长度。摆动子序列是指相邻元素的差在正负之间交替变化。第一个差值可以是正数或负数。如果只有一个元素，那么它也被视为一个摆动序列。
示例：
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列 [1,7,4,9,2,5] 就是一个摆动序列，因为差值 (6,-3,5,-7,3) 正负交替。
解题过程：
- 问题分析：
- 我们需要找到一个子序列（不一定连续），使得相邻元素的差值正负交替
- 对于位置 i，我们需要考虑以 i 结尾的摆动子序列的两种状态：
- 以上升结束（最后一个差值为正）
- 以下降结束（最后一个差值为负）
- 状态定义：
定义两个 DP 数组：
- up[i]：表示以第 i 个元素结尾，且最后呈上升趋势的最长摆动子序列长度
- down[i]：表示以第 i 个元素结尾，且最后呈下降趋势的最长摆动子序列长度
- 状态转移方程：
对于每个位置 i，我们需要考虑所有 j < i 的情况：
- 如果 nums[i] > nums[j]：
- up[i] = max(up[i], down[j] + 1)
- 因为当前是上升，所以只能接在下降序列后面
- 如果 nums[i] < nums[j]：
- down[i] = max(down[i], up[j] + 1)
- 因为当前是下降，所以只能接在上升序列后面
- 初始化：
- 每个位置初始的最短长度都是 1（只包含自己）
- up[0] = 1, down[0] = 1
- 算法步骤：
- 初始化 up 和 down 数组，长度都为 n，值都为 1
- 遍历 i 从 1 到 n-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)
- 如果 nums[i] > nums[j]：
- 遍历 j 从 0 到 i-1：
- 最终结果是 max(up[n-1], down[n-1])
- 时间复杂度优化：
上面的解法是 O(n²)，我们可以优化到 O(n)：
- 只需要维护两个变量：up 和 down
- 遍历数组，根据当前元素与前一个元素的关系更新：
- 如果 nums[i] > nums[i-1]：up = down + 1
- 如果 nums[i] < nums[i-1]：down = up + 1
- 优化后的算法：
- up = 1, down = 1
- 遍历 i 从 1 到 n-1：
- 如果 nums[i] > nums[i-1]：
- up = down + 1
- 如果 nums[i] < nums[i-1]：
- down = up + 1
- 如果 nums[i] > nums[i-1]：
- 返回 max(up, down)
这种优化利用了摆动序列的贪心性质：我们总是希望尽可能早地改变趋势，从而获得更长的序列。