시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 147 | 98 | 57 | 69.512% |
A sequence of integers is said to Zigzag if adjacent elements alternate between strictly increasing and strictly decreasing. Note that the sequence may start by either increasing or decreasing. Given a sequence of integers, determine the length of the longest subsequence that Zigzags. For example, consider this sequence:
1 2 3 4 2
There are several Zigzagging subsequences of length 3:
1 3 2 1 4 2 2 3 2 2 4 2 3 4 2
But there are none of length greater than 3, so the answer is 3.
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains an integer n (1 ≤ n ≤ 1,000,000) which is the number of integers in the list. Each of the following n lines will have an integer k (1 ≤ k ≤ 1,000,000)
Output a single integer, which is the length of the longest Zigzagging subsequence of the input list.
5 1 2 3 4 2
3
6 1 1 1 1 1 1
1
ICPC > Regionals > North America > Southeast USA Regional > 2016 Southeast USA Regional Programming Contest > Division 1 K번
ICPC > Regionals > North America > Southeast USA Regional > 2016 Southeast USA Regional Programming Contest > Division 2 K번
ICPC > Regionals > North America > Pacific Northwest Regional > 2016 Pacific Northwest Region Programming Contest > Division 2 Y번