g6-07892. 摆动序列 · 林老师的题库

题目描述

给定长度为 $n$ 的整数数组 $a_{1}, \dots, a_{n}$ 。从数组中删去一些元素（也可以不删），剩下的元素保持原顺序，得到一个子序列。如果子序列相邻两个元素的差正负交替出现，就称为摆动序列：

a_{i_{1}} < a_{i_{2}} > a_{i_{3}} < a_{i_{4}} > \dots

或者

a_{i_{1}} > a_{i_{2}} < a_{i_{3}} > a_{i_{4}} < \dots

相等的相邻元素不算一次交替。求最长摆动子序列的长度。

第一行一个整数 $n$ 。

第二行 $n$ 个整数 $a_{i}$ 。

一行一个整数，表示最长摆动子序列的长度。

6
1 7 4 9 2 5

$1 \leq n \leq 1 0^{5}$ ， $1 \leq a_{i} \leq 1 0^{4}$ 。