Longest Alternating Subsequence
Given a sequence of N integers, find the length of the longest subsequence such that the elements alternate in strictly increasing and decreasing order. That is, for a subsequence a[i_1], a[i_2], ..., a[i_k], we must have a[i_1] < a[i_2] > a[i_3] < a[i_4] > ... or a[i_1] > a[i_2] < a[i_3] > a[i_4] < ....
A subsequence is formed by deleting zero or more elements from the original sequence without changing the order of the remaining elements.
Input
The first line contains an integer N, the size of the sequence. The second line contains N space-separated integers representing the sequence.
Output
Print a single integer, the length of the longest alternating subsequence.
Constraints
1 <= N <= 200000 -10^9 <= a[i] <= 10^9
Example 1
5 1 5 2 8 3
5
The longest alternating subsequence is 1, 5, 2, 8, 3 itself, with length 5.
Example 2
7 10 20 15 25 30 20 10
5
The longest alternating subsequences include 10, 20, 15, 30, 10 (length 5) or 10, 20, 15, 25, 20, 10 (length 6). The latter is longer.
Hints
Similar problems
- Maximum Sum of Consecutive SubsegmentsMedium
- Maximum Sum of Non-Adjacent SubarraysMedium
- Maximum Sum of Non-overlapping SubarraysMedium
- Max Consecutive SumMedium
- Maximum Sum of Non-Adjacent Elements in a Circular ArrayMedium
- Maximum Sum of Non-Overlapping SubsegmentsMedium
More topics: Greedy problems, Dynamic Programming problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 5 2 8 3
7 10 20 15 25 30 20 10