最长交替子序列（Longest Alternating Subsequence）
字数 2440 2025-12-11 07:23:37

最长交替子序列（Longest Alternating Subsequence）

题目描述
给定一个整数数组 nums，找出其中最长的交替子序列的长度。一个序列被称为“交替”的，如果相邻元素之间的差值正负交替出现。也就是说，对于子序列中的连续三个元素 a, b, c，如果 b > a，则必须有 c < b；如果 b < a，则必须有 c > b。换句话说，交替子序列中相邻元素的大小关系必须一升一降（或一降一升）交替出现。子序列不要求连续，但顺序必须保持原数组中的相对顺序。

例如：

  • 输入：nums = [1, 5, 4, 7, 2, 9]
  • 输出：5
  • 解释：最长交替子序列之一是 [1, 5, 4, 7, 2]，相邻差值符号为 + - + -。

解题思路
这是一个经典的线性动态规划问题。我们可以定义两个状态数组，分别表示以某个位置结尾、且最后一步是上升或下降的最长交替子序列长度。

步骤分解

步骤1：定义状态
设：

  • up[i]：以 nums[i] 结尾，且最后一步是“上升”（即 nums[i] 比前一个元素大）的最长交替子序列的长度。
  • down[i]：以 nums[i] 结尾，且最后一步是“下降”（即 nums[i] 比前一个元素小）的最长交替子序列的长度。

步骤2：初始状态
对于任意位置 i，至少可以单独取自己作为一个子序列，因此：
up[i] = 1
down[i] = 1
（因为单独一个元素，既没有上升也没有下降，但为了统一，我们初始化为1，表示长度为1的子序列。）

步骤3：状态转移
我们遍历数组，对于每个位置 i，我们考虑所有前面的位置 j（j < i）：

  • 如果 nums[i] > nums[j]，说明在 j 处可以是下降结尾，然后接上 nums[i] 形成上升。因此：
    up[i] = max(up[i], down[j] + 1)
  • 如果 nums[i] < nums[j]，说明在 j 处可以是上升结尾，然后接上 nums[i] 形成下降。因此：
    down[i] = max(down[i], up[j] + 1)

步骤4：计算顺序
由于状态 up[i] 和 down[i] 依赖于前面所有位置的状态，我们按 i 从 0 到 n-1 顺序计算即可。

步骤5：最终答案
最长交替子序列的长度是 max(up[i], down[i]) 对所有 i 取最大值。

示例推演
以 nums = [1, 5, 4, 7, 2, 9] 为例：

初始化：

i=0: up=1, down=1

计算 i=1（元素5）：

  • 比较 j=0：5 > 1 → up[1] = max(1, down[0]+1) = max(1, 1+1) = 2
  • 没有下降情况，down[1] 保持1
    → up=2, down=1

计算 i=2（元素4）：

  • 比较 j=0：4 > 1 → up[2] = max(1, down[0]+1) = 2
  • 比较 j=1：4 < 5 → down[2] = max(1, up[1]+1) = max(1, 2+1) = 3
    → up=2, down=3

计算 i=3（元素7）：

  • 比较 j=0：7 > 1 → up[3] = max(1, down[0]+1) = 2
  • 比较 j=1：7 > 5 → up[3] = max(2, down[1]+1) = max(2, 1+1)=2
  • 比较 j=2：7 > 4 → up[3] = max(2, down[2]+1) = max(2, 3+1)=4
  • 没有下降情况，down[3] 保持1
    → up=4, down=1

计算 i=4（元素2）：

  • 比较 j=0：2 > 1 → up[4] = max(1, down[0]+1) = 2
  • 比较 j=1：2 < 5 → down[4] = max(1, up[1]+1) = max(1, 2+1)=3
  • 比较 j=2：2 < 4 → down[4] = max(3, up[2]+1) = max(3, 2+1)=3
  • 比较 j=3：2 < 7 → down[4] = max(3, up[3]+1) = max(3, 4+1)=5
    → up=2, down=5

计算 i=5（元素9）：

  • 比较 j=0：9 > 1 → up[5] = max(1, down[0]+1) = 2
  • 比较 j=1：9 > 5 → up[5] = max(2, down[1]+1) = 2
  • 比较 j=2：9 > 4 → up[5] = max(2, down[2]+1) = max(2, 3+1)=4
  • 比较 j=3：9 > 7 → up[5] = max(4, down[3]+1) = max(4, 1+1)=4
  • 比较 j=4：9 > 2 → up[5] = max(4, down[4]+1) = max(4, 5+1)=6
    → up=6, down=1

最终，所有 up 和 down 的最大值是6，对应子序列 [1, 5, 4, 7, 2, 9]（差值符号：+ - + - +），长度为6。

复杂度分析

  • 时间复杂度：O(n²)，因为对每个 i，我们比较了所有 j < i。
  • 空间复杂度：O(n)，用于存储 up 和 down 数组。

优化思考
实际上，我们可以在一次遍历中只记录当前全局的最长上升结尾和下降结尾的长度，将复杂度优化到 O(n)，但标准的动态规划解法更直观易懂。如果你希望，我也可以为你讲解 O(n) 的贪心优化解法。

最长交替子序列（Longest Alternating Subsequence） 题目描述 给定一个整数数组 nums ，找出其中最长的交替子序列的长度。一个序列被称为“交替”的，如果相邻元素之间的差值正负交替出现。也就是说，对于子序列中的连续三个元素 a, b, c ，如果 b > a ，则必须有 c < b ；如果 b < a ，则必须有 c > b 。换句话说，交替子序列中相邻元素的大小关系必须一升一降（或一降一升）交替出现。子序列不要求连续，但顺序必须保持原数组中的相对顺序。 例如： 输入： nums = [1, 5, 4, 7, 2, 9] 输出： 5 解释：最长交替子序列之一是 [1, 5, 4, 7, 2] ，相邻差值符号为 + - + - 。 解题思路 这是一个经典的线性动态规划问题。我们可以定义两个状态数组，分别表示以某个位置结尾、且最后一步是上升或下降的最长交替子序列长度。 步骤分解 步骤1：定义状态 设： up[i] ：以 nums[i] 结尾，且最后一步是“上升”（即 nums[i] 比前一个元素大）的最长交替子序列的长度。 down[i] ：以 nums[i] 结尾，且最后一步是“下降”（即 nums[i] 比前一个元素小）的最长交替子序列的长度。 步骤2：初始状态 对于任意位置 i ，至少可以单独取自己作为一个子序列，因此： up[i] = 1 down[i] = 1 （因为单独一个元素，既没有上升也没有下降，但为了统一，我们初始化为1，表示长度为1的子序列。） 步骤3：状态转移 我们遍历数组，对于每个位置 i ，我们考虑所有前面的位置 j （ j < i ）： 如果 nums[i] > nums[j] ，说明在 j 处可以是下降结尾，然后接上 nums[i] 形成上升。因此： up[i] = max(up[i], down[j] + 1) 如果 nums[i] < nums[j] ，说明在 j 处可以是上升结尾，然后接上 nums[i] 形成下降。因此： down[i] = max(down[i], up[j] + 1) 步骤4：计算顺序 由于状态 up[i] 和 down[i] 依赖于前面所有位置的状态，我们按 i 从 0 到 n-1 顺序计算即可。 步骤5：最终答案 最长交替子序列的长度是 max(up[i], down[i]) 对所有 i 取最大值。 示例推演 以 nums = [1, 5, 4, 7, 2, 9] 为例： 初始化： 计算 i=1 （元素5）： 比较 j=0 ： 5 > 1 → up[1] = max(1, down[0]+1) = max(1, 1+1) = 2 没有下降情况， down[1] 保持1 → up=2, down=1 计算 i=2 （元素4）： 比较 j=0 ： 4 > 1 → up[2] = max(1, down[0]+1) = 2 比较 j=1 ： 4 < 5 → down[2] = max(1, up[1]+1) = max(1, 2+1) = 3 → up=2, down=3 计算 i=3 （元素7）： 比较 j=0 ： 7 > 1 → up[3] = max(1, down[0]+1) = 2 比较 j=1 ： 7 > 5 → up[3] = max(2, down[1]+1) = max(2, 1+1)=2 比较 j=2 ： 7 > 4 → up[3] = max(2, down[2]+1) = max(2, 3+1)=4 没有下降情况， down[3] 保持1 → up=4, down=1 计算 i=4 （元素2）： 比较 j=0 ： 2 > 1 → up[4] = max(1, down[0]+1) = 2 比较 j=1 ： 2 < 5 → down[4] = max(1, up[1]+1) = max(1, 2+1)=3 比较 j=2 ： 2 < 4 → down[4] = max(3, up[2]+1) = max(3, 2+1)=3 比较 j=3 ： 2 < 7 → down[4] = max(3, up[3]+1) = max(3, 4+1)=5 → up=2, down=5 计算 i=5 （元素9）： 比较 j=0 ： 9 > 1 → up[5] = max(1, down[0]+1) = 2 比较 j=1 ： 9 > 5 → up[5] = max(2, down[1]+1) = 2 比较 j=2 ： 9 > 4 → up[5] = max(2, down[2]+1) = max(2, 3+1)=4 比较 j=3 ： 9 > 7 → up[5] = max(4, down[3]+1) = max(4, 1+1)=4 比较 j=4 ： 9 > 2 → up[5] = max(4, down[4]+1) = max(4, 5+1)=6 → up=6, down=1 最终，所有 up 和 down 的最大值是6，对应子序列 [1, 5, 4, 7, 2, 9] （差值符号： + - + - + ），长度为6。 复杂度分析 时间复杂度：O(n²)，因为对每个 i ，我们比较了所有 j < i 。 空间复杂度：O(n)，用于存储 up 和 down 数组。 优化思考 实际上，我们可以在一次遍历中只记录当前全局的最长上升结尾和下降结尾的长度，将复杂度优化到 O(n)，但标准的动态规划解法更直观易懂。如果你希望，我也可以为你讲解 O(n) 的贪心优化解法。