最长锯齿子序列(Longest Zigzag Subsequence)

题目描述

给定 $n$ 个整数组成的序列 $a_1, a_2, \cdots, a_n$，请从中挑出尽量长的子序列，形成一个锯齿序列。所谓锯齿序列，就是它的差分序列（由相邻数字的差组成的序列）是正负交替的。为了避免差为 0 时不方便区分正负，保证给定的每个数字都不相同。

例如给定的序列是 $1, 3, 5, 2, 4, 6$，那么它的子序列 $1, 5, 2, 6$ 是一个锯齿序列，因为它的差分序列是 $4, -3, 4$；而 $1, 3, 5$ 不是，因为这三个数字是递增的。

输入格式

第一行：一个整数 $n$

第二行：$n$ 个整数 $a_1, a_2, \cdots, a_n$

输出格式

单个整数：表示最长的锯齿子序列长度

样例输入 #1

6
1 3 5 2 4 6

样例输出 #1

4

数据范围

对于 30% 的数据：$1 \leq n \leq 10$

对于 60% 的数据：$1 \leq n \leq 10^3$

对于 100% 的数据：$1 \leq n \leq 10^4$，$1 \leq a_i \leq 10^5$

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐。

测试点分布