Statement

The Longest Alternating Subsequence (LAS) is the longest subsequence from a given array, in which the subsequence elements are in alternating order. Given an integer array, nums, find the length of the LAS in this array.

Let’s say we have an integer array, [4, 1, 5, 6, 3, 2, 1], and we want to get the longest alternating subsequence in this array. There are multiple alternating subsequences of different lengths, such as [4, 1], [1, 5], [5, 3], [4, 3], [4, 1, 5], [4, 1, 5, 3], [4, 1, 6], [4, 1, 6, 1], and so on. We observe that [4, 5, 6], [4, 3, 2, 1], and [4, 6, 3, 2, 1] are not alternating subsequences. The longest alternating subsequences, in this case, are [4, 1, 5, 3], [4, 1, 5, 2], [4, 1, 5, 1], [4, 1, 6, 3], [4, 1, 6, 2] and [4, 1, 6, 1], all of length 4.

Constraints:

  • 11 \leq nums.length 900\leq 900
  • 104-10^4 \leq nums[i] 104\leq 10^4

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.