Longest Zigzag Subsequence
Given a sequence of integers, find the length of the longest subsequence such that the differences between consecutive elements strictly alternate in sign. The first difference can be positive or negative. A subsequence is formed by deleting zero or more elements from the original sequence without changing the order of the remaining elements.
For example, in the sequence [1, 5, 2, 8, 3, 4, 7, 6, 9], a zigzag subsequence is [1, 5, 2, 8, 3, 7, 6, 9]. The differences are (5-1)=4, (2-5)=-3, (8-2)=6, (3-8)=-5, (7-3)=4, (6-7)=-1, (9-6)=3. The signs of differences are +, -, +, -, +, -, +.
If the sequence has fewer than two elements, the longest zigzag subsequence has the same length as the sequence.
Input
The first line contains an integer N, the length of the sequence. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print a single integer, the length of the longest zigzag subsequence.
Constraints
1 <= N <= 200000 -10^9 <= A_i <= 10^9
Example 1
9 1 5 2 8 3 4 7 6 9
8
The longest zigzag subsequence is [1, 5, 2, 8, 3, 7, 6, 9], length 8.
Example 2
5 1 2 3 4 5
2
The longest zigzag subsequence can be [1, 2] or [2, 3] etc., length 2.
Hints
Similar problems
- Maximum Sum Increasing SubsequenceMedium
- Maximum Sum Non-Adjacent PairsMedium
- Lexicographically Smallest PathMedium
- Count Subsequences Summing to KEasy
- Longest Increasing Subsequence on a PermutationHard
- Count Paths on a LineEasy
More topics: Dynamic Programming problems, Recursion problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
9 1 5 2 8 3 4 7 6 9
5 1 2 3 4 5