# Longest Alternating Subsequence

Let's solve the Longest Alternating Subsequence problem using Dynamic Programming.

## 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:**

- $1 \leq$
`nums.length`

$\leq 10^3$ - $-10^4 \leq$
`nums[i]`

$\leq 10^4$

## Examples

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