#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 个元素为最大值的最长优美子序列的长度。注意,优美子序列的长度必须为奇数,且中位数为其最大值。

解析

解题思路

本题要求找出一个序列中最长的优美子序列,优美子序列的定义为:

  1. 长度为奇数;
  2. 中位数为最大值。

为了满足优美子序列的条件,我们需要构建一个动态规划数组 dp,其中 dp[i] 表示以 a[i] 为最大值的最长优美子序列的长度。通过遍历序列,我们尝试找到每一个元素之前的所有小于它的元素,并更新 dp 数组。

最后,我们从后往前遍历 dp 数组,找到长度为奇数的最大值作为答案。

算法选择理由

动态规划是解决最优子结构问题的有效方法。本题中,优美子序列的定义天然具有最优子结构,即每一个以某元素为最大值的优美子序列,可以由其子序列推导出来。我们通过维护一个 dp 数组,记录每一个元素作为最大值的优美子序列的最大长度,从而保证了最优解的构建。

复杂度分析

  • 时间复杂度:O(n^2),其中 n 是序列的长度。对于每一个元素,我们需要遍历它之前的所有元素来更新 dp 数组。
  • 空间复杂度:O(n),我们需要一个 dp 数组和一个辅助数组 last 来存储中间结果。

本算法在实际应用中可以通过优化减少时间复杂度,例如使用二分查找或树状数组来加速查找过程,但此处的 O(n^2) 算法已经足够解决给定的最大规模数据。

来源

AI 生成 · qwen2.5:14b · 普及+/提高- · 动态规划