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

📘 题目描述

给定一个长度为 n 的整数数组 a[1..n]，请你找出一个​最长的交替子序列​。

所谓交替子序列，指的是一个子序列中元素满足​严格的“上升下降交替”或“下降上升交替​：

• 例如：[1, 5, 3, 6, 2] 是交替的（上升 → 下降 → 上升 → 下降）；
• 但 [1, 3, 5, 7] 不是交替的。

📥 输入格式

• 第一行一个整数 n（1 ≤ n ≤ 1000），表示数组长度；
• 第二行 n 个整数 a[1..n]，表示数组中的元素。

📤 输出格式

• 输出一个整数，表示最长交替子序列的长度。

💡 输入输出样例

输入样例 #1

6
1 5 4 3 6 2

输出样例 #1

5

解释：最长交替子序列为 [1, 5, 3, 6, 2]

输入样例 #2

5
10 22 9 33 21

输出样例 #2

4

🧠 解题思路（动态规划）

我们定义两个数组来处理“最后是上升”和“最后是下降”的情况：

• up[i]：以 a[i] 结尾，最后一个是上升的交替子序列的最长长度；
• down[i]：以 a[i] 结尾，最后一个是下降的交替子序列的最长长度。

状态转移方程：

if (a[j] < a[i]) up[i] = max(up[i], down[j] + 1);      // a[j] 下降 → a[i] 上升
if (a[j] > a[i]) down[i] = max(down[i], up[j] + 1);    // a[j] 上升 → a[i] 下降

初始化：

up[i] = down[i] = 1;  // 每个单独元素是长度为1的交替序列

📊 时间与空间复杂度

• 时间复杂度：O(n²)
• 空间复杂度：O(n)

✅ 边界测试建议