Longest Alternating Subsequence Problem – II
Given an integer array, find the length of the longest subsequence with alternate low and high elements in the array.
For example,
Output: 6
Explanation: There are several subsequences with alternate low and high elements having length 6:
[8, 9, 6, 7, 3, 4]
[8, 9, 6, 7, 2, 4]
[8, 9, 4, 7, 3, 4]
[8, 9, 4, 7, 2, 4]
…
The idea is to traverse the array from left to right and keep track of the longest alternating sequence that ends at the element you are currently at. We update two counters, low and high, for each index in the array since the current element in the final maximum length alternating sequence can be either low or high. Now, we update high = low + 1 if the current element is greater than its previous element and update low = high + 1 if the current element is less than the previous element. Don’t update low or high if the current element is the same as the preceding element because the problem targets only subsequences, not subarrays.
Following is the C++, Java, and Python implementation based on the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Function to find the length of the longest subsequence with alternate // low and high elements int findLongestSequence(vector<int> const &nums) { // base case if (nums.size() == 0) { return 0; } // initialize high and low with 1 (for the first element) int high = 1, low = 1; // keep track of the previous element int prev = nums[0]; // start with the second element of the array for (int i = 1; i < nums.size(); i++) { int curr = nums[i]; // if current element is less than the previous element if (curr < prev) { low = high + 1; } // if the current element is more than the previous element else if (curr > prev) { high = low + 1; } // update the previous element prev = curr; } // return the maximum of the two return max(high, low); } int main() { vector<int> nums = { 8, 9, 6, 4, 5, 7, 3, 2, 4 }; cout << "The length of the longest alternating subsequence is " << findLongestSequence(nums); return 0; } |
Output:
The length of the longest alternating subsequence is 6
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Main { // Function to find the length of the longest subsequence with alternate // low and high elements public static int findLongestSequence(int[] nums) { // base case if (nums.length == 0) { return 0; } // initialize high and low with 1 (for the first element) int high = 1, low = 1; // keep track of the previous element int prev = nums[0]; // start with the second element of the array for (int i = 1; i < nums.length; i++) { int curr = nums[i]; // if current element is less than the previous element if (curr < prev) { low = high + 1; } // if the current element is more than the previous element else if (curr > prev) { high = low + 1; } // update the previous element prev = curr; } // return the maximum of the two return Integer.max(high, low); } public static void main(String[] args) { int[] nums = { 8, 9, 6, 4, 5, 7, 3, 2, 4 }; System.out.println("The length of the longest alternating subsequence is " + findLongestSequence(nums)); } } |
Output:
The length of the longest alternating subsequence is 6
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
# Function to find the length of the longest subsequence with alternate low and high def findLongestSequence(nums): # base case if not nums: return 0 # initialize high and low with 1 (for the first element) low = high = 1 # keep track of the previous element prev = nums[0] # start with the second element of the array for i in range(1, len(nums)): curr = nums[i] # if current element is less than the previous element if curr < prev: low = high + 1 # if the current element is more than the previous element elif curr > prev: high = low + 1 # update the previous element prev = curr # return the maximum of the two return max(high, low) if __name__ == '__main__': nums = [8, 9, 6, 4, 5, 7, 3, 2, 4] print('The length of the longest alternating subsequence is', findLongestSequence(nums)) |
Output:
The length of the longest alternating subsequence is 6
The time complexity of the above solution is O(n) and requires O(1) extra space, where n is the length of the array.
Because of the way this algorithm uses optimal substructure (the longest alternating sequence ending at each position is calculated merely from a related but smaller and overlapping subproblem: the longest alternating sequence ending at the previous position), this algorithm can be viewed as a simple example of dynamic programming.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)