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:
-
nums.length -
nums[i]
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.
import java.util.*;public class LAS{public static Integer LAS(int[] nums) {// Write your code here// your code will replace this placeholder return statementreturn -1;}}
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 ...