2083. ZigZag

单点时限: 2.0 sec

内存限制: 256 MB

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

输入格式

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

  • sequence contains between 1 and 50 elements, inclusive.
  • Each element of sequence is between 1 and 1000, inclusive.

输出格式

output the length of the longest subsequence of sequence that is a zig-zag sequence.

样例

Input
10
1 17 5 10 13 15 10 5 16 8
Output
7
Input
6
1 7 4 9 2 5
Output
6

198 人解决,223 人已尝试。

294 份提交通过,共有 691 份提交。

2.2 EMB 奖励。

创建: 12 年,8 月前.

修改: 3 年,1 月前.

最后提交: 1 周,2 天前.

来源: TC

题目标签
DP