P15442 [蓝桥杯 2025 国研究生组] 山峰子序列

C/C++/Python 研究生组

一个序列 $T = [t_1, t_2, \cdots, t_k]$ 是“山峰序列”当且仅当存在一个长度为 $m$（$m$ 可任意选）的下标对序列 $(l_1, r_1), (l_2, r_2), \cdots, (l_m, r_m)$ 满足： - $l_1 = 1$ 且 $r_m = k$； - $r_i > l_i$； - $r_{i-1} + 1 = l_i$； - $r_i - l_i \equiv 0 \pmod{2}$ 且 $t_{(l_i + r_i)/2}$ 是序列 $T$ 在区间 $[l_i, r_i]$ 中的最大值； - 序列 $T$ 在区间 $[l_i, \dfrac{l_i + r_i}{2}]$ 严格单调递增，在区间 $[\dfrac{l_i + r_i}{2}, r_i]$ 严格单调递减。 给定一个长度为 $n$ 的整数数组 $[a_1, a_2, \cdots, a_n]$，求其最长的子序列 $T$ 满足 $T$ 是“山峰序列”，输出其长度。 **说明**：下标对序列 $(l_i, r_i)$ 基于子序列 $T$ 的下标，$T$ 的下标从 1 开始。

输入的第一行包含一个正整数 $n$。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，相邻整数之间使用一个空格分隔。

输出一行包含一个整数表示答案。

### 样例说明 可取子序列 $T = [1, 3, 2, 4, 1, 2, 3, 4, 3, 1]$，其长度为 10 且为一个“山峰序列”，下标对序列为 $(1, 3), (4, 8)$。 ### 评测用例规模与约定 对于 $20\%$ 的评测用例，$1 \le n \le 50$； 对于 $40\%$ 的评测用例，$1 \le n \le 200$； 对于所有评测用例，$1 \le n \le 2000$，$0 \le a_i \le 10^6$。