Search⌘ K
Home
Courses
Grokking Dynamic Programming Interview in Python

Longest Alternating Subsequence

Explore how to identify and solve the Longest Alternating Subsequence problem using dynamic programming. Understand the naive recursive method and optimize it with top-down memoization and bottom-up tabulation to improve time and space efficiency. This lesson helps you master a common interview pattern in sequence optimization.

We'll cover the following...

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≤1 \leq nums.length ≤900\leq 900
  • −104≤-10^4 \leq nums[i] ≤104\leq 10^4

Examples

No.

Input

Output

LAS

1

[3, 1, 5, 2]

4

[3, 1, 5, 2]

2

[10, 30, 50, 70]

2

[10, 30], [30, 50], [50, 70], [10, 50], [10, 70], [30, 70]

3

[5, 5, 5, 5, 5, 5, 5]

1

[5]

4

[4, 1, 5, 6, 3, 2, 1]

4

[4, 1, 5, 3], [4, 1, 5, 2], [4, 1, 5, 1], [4, 1, 6, 3], [4, 1, 6, 2], [4, 1, 6, 1]

Try it yourself

Implement your solution in the following playground.

Python
usercode > main.py
def LAS(nums):



    # Write your code here

    

    return -1
Longest Alternating Subsequence

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach

Let’s consider how we might write a recursive solution to this problem. We need to move from the start of the list to the end, and we need to consider all the elements. Any given element is either in the current subsequence or not, and our solution needs to evaluate both cases. So, for every current element in the list, we will have three options:

  1. If the current element is bigger than the previous element, we include the current element and ...