#3722. 最长优美子序列
最长优美子序列
题目描述
给定一个长度为 n 的整数序列 a。若一个子序列满足以下条件,则称其为优美子序列:
- 子序列的长度为奇数;
- 子序列的中位数为其最大值。 你的任务是找到给定序列中最长的优美子序列,输出其长度。
例如,序列 [1,2,3,4,5] 中,[1,2,3,4,5] 和 [3] 都是优美子序列,但 [1,3,5] 不是,因为它的中位数不是最大值。
示例输入: 5 1 2 3 4 5
示例输出: 5
解释:最长优美子序列是整个序列本身。
注意:你需要输出最长优美子序列的长度,而非子序列本身。
输入格式
第一行一个整数 n (1 ≤ n ≤ 10^5)。 第二行 n 个整数 a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9)。
输出格式
输出一个整数,表示最长优美子序列的长度。
样例
5
1 2 3 4 5
5
7
1 3 5 4 2 6 7
5
说明/提示
本题可以通过动态规划解决,定义 dp[i] 表示以第 i 个元素为最大值的最长优美子序列的长度。注意,优美子序列的长度必须为奇数,且中位数为其最大值。
解析
解题思路
本题要求找出一个序列中最长的优美子序列,优美子序列的定义为:
- 长度为奇数;
- 中位数为最大值。
为了满足优美子序列的条件,我们需要构建一个动态规划数组 dp,其中 dp[i] 表示以 a[i] 为最大值的最长优美子序列的长度。通过遍历序列,我们尝试找到每一个元素之前的所有小于它的元素,并更新 dp 数组。
最后,我们从后往前遍历 dp 数组,找到长度为奇数的最大值作为答案。
算法选择理由
动态规划是解决最优子结构问题的有效方法。本题中,优美子序列的定义天然具有最优子结构,即每一个以某元素为最大值的优美子序列,可以由其子序列推导出来。我们通过维护一个 dp 数组,记录每一个元素作为最大值的优美子序列的最大长度,从而保证了最优解的构建。
复杂度分析
- 时间复杂度:O(n^2),其中 n 是序列的长度。对于每一个元素,我们需要遍历它之前的所有元素来更新 dp 数组。
- 空间复杂度:O(n),我们需要一个 dp 数组和一个辅助数组 last 来存储中间结果。
本算法在实际应用中可以通过优化减少时间复杂度,例如使用二分查找或树状数组来加速查找过程,但此处的 O(n^2) 算法已经足够解决给定的最大规模数据。
来源
AI 生成 · qwen2.5:14b · 普及+/提高- · 动态规划