Back to course home
0% completed
Solution: Longest Alternating Subsequence
Problem Statement
Given a number sequence, find the length of its Longest Alternating Subsequence (LAS). A subsequence is considered alternating if its elements are in alternating order.
A three element sequence (a1, a2, a3) will be an alternating sequence if its elements hold one of the following conditions:
{a1 > a2 < a3 } or { a1 < a2 > a3}.
Example 1:
Input: {1,2,3,4}
Output: 2
Explanation: There are many LAS: {1,2}, {3,4}, {1,3}, {1,4}
Example 2:
Input: {3,2,1,4}
Output: 3
Explanation: The LAS are {3,2,4} and {2,1,4}.
Example 3:
.....
.....
.....
Like the course? Get enrolled and start learning!