Longest Alternating Subsequence is a problem of finding a subsequence of a given sequence in which the elements are in alternating order, and in which the sequence is as long as possible.

In order words, we need to find the length of longest subsequence with alternate low and high elements.

The problem differs from problem of finding longest alternating subarray. Unlike subarrays, subsequences are not required to occupy consecutive positions within the original sequences.

For example, consider array A[] = [8, 9, 6, 4, 5, 7, 3, 2, 4]

The length of longest subsequence is 6 and the subsequence is [8, 9, 6, 7, 3, 4] as

(8 < 9 > 6 < 7 > 3 < 4)

Note that the Longest Subsequence is not unique. Below are few more subsequences of length 6 –

(8, 9, 6, 7, 2, 4)

(8, 9, 4, 7, 3, 4)

(8, 9, 4, 7, 2, 4)

…

…

and many more..

We can use Recursion to solve this problem. The idea is to maintain a flag to indicate if next element in the sequence should be smaller or greater than the previous element. Then for any element arr[i] at index i, we have two choices –

1. We include the element in the subsequence.

- if the flag is true and arr[i-1] < arr[i], we include arr[i] as next high in the subsequence
- if the flag is false and arr[i-1] > arr[i], we include arr[i] as next low in the subsequence

2. We exclude the element in subsequence.

## 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 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include <string> using namespace std; // Util function to find length of longest alternating subsequence // if flag is true, next element should be greater // if flag is false, next element should be smaller int Util(int arr[], int start, int end, bool flag) { int res = 0; for (int i = start; i <= end; i++) { // include arr[i] as next high in subsequence and flip flag // for next subsequence if (flag && arr[i - 1] < arr[i]) res = max(res, 1 + Util(arr, i + 1, end, !flag)); // include arr[i] as next low in subsequence and flip flag // for next subsequence else if (!flag && arr[i - 1] > arr[i]) res = max(res, 1 + Util(arr, i + 1, end, !flag)); // don't include arr[i] in subsequence else res = max(res, Util(arr, i + 1, end, flag)); } return res; } // Function to find length of longest subsequence with alternate // low and high elements. It uses Util() method. int findLongestSequence(int arr[], int n) { // Fix first element and recurse for remaining elements as first // element will always be part of longest subsequence (why?) // There are two possibilities - // 1. Next element is greater (pass true) // 2. Next element is smaller (pass false) return 1 + max(Util(arr, 1, n - 1, true), Util(arr, 1, n - 1, false)); // instead of fixing first element, we can also directly call // return max(Util(arr, 0, n, true), Util(arr, 0, n, false)); } // main function int main() { int arr[] = { 8, 9, 6, 4, 5, 7, 3, 2, 4 }; int n = sizeof(arr) / sizeof(arr[0]); // Find Longest alternating subsequence cout << "The length of Longest Subsequence is " << findLongestSequence(arr, n); return 0; } |

`Output:`

The length of Longest 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 47 48 49 50 51 52 53 54 55 56 |
class LongestSequence { // Util function to find length of longest subsequence // if flag is true, next element should be greater // if flag is false, next element should be smaller public static int Util(int[] A, int start, int end, boolean flag) { int res = 0; for (int i = start; i <= end; i++) { // include A[i] as next high in subsequence and flip flag // for next subsequence if (flag && A[i - 1] < A[i]) { res = Integer.max(res, 1 + Util(A, i + 1, end, !flag)); } // include A[i] as next low in subsequence and flip flag // for next subsequence else if (!flag && A[i - 1] > A[i]) { res = Integer.max(res, 1 + Util(A, i + 1, end, !flag)); } // don't include A[i] in subsequence else { res = Integer.max(res, Util(A, i + 1, end, flag)); } } return res; } // Function to find length of longest subsequence with alternate // low and high elements. It uses Util() method. public static int findLongestSequence(int[] arr) { // Fix first element and recurse for remaining elements as first // element will always be part of longest subsequence (why?) // There are two possibilities - // 1. Next element is greater (pass true) // 2. Next element is smaller (pass false) return 1 + Integer.max(Util(arr, 1, arr.length - 1, true), Util(arr, 1, arr.length - 1, false)); // instead of fixing first element, we can also directly call // return max(Util(arr, 0, n, true), Util(arr, 0, n, false)); } // main function public static void main(String[] args) { int[] A = { 8, 9, 6, 4, 5, 7, 3, 2, 4 }; System.out.println("The length of Longest Subsequence is " + findLongestSequence(A)); } } |

`Output:`

The length of Longest Subsequence is 6

The time complexity of above solution is exponential and auxiliary space used by the program is O(1).

The LAS problem has an optimal substructure and also exhibits overlapping subproblems. We know that problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are saved rather than computed over and over again. This method is illustrated below which follows top-down approach using *Memo*ization.

## 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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <iostream> #include <string> using namespace std; // define max number of elements in array #define N 10 // lookup table to store solutions of subproblem // max(lookup[i][0], lookup[i][1]) stores longest sequence // till arr[0..i] int lookup[N][2]; // Util function to find length of longest alternating subsequence // if flag is true, next element should be greater // if flag is false, next element should be smaller int Util(int arr[], int start, int end, bool flag) { // if sub-problem is seen for the first time, solve it and // store its result in lookup table if (lookup[start][flag] == 0) { int res = 0; for (int i = start; i <= end; i++) { // include arr[i] as next high in subsequence and flip flag // for next subsequence if (flag && arr[i - 1] < arr[i]) res = max(res, 1 + Util(arr, i + 1, end, !flag)); // include arr[i] as next low in subsequence and flip flag // for next subsequence else if (!flag && arr[i - 1] > arr[i]) res = max(res, 1 + Util(arr, i + 1, end, !flag)); // don't include arr[i] in subsequence else res = max(res, Util(arr, i + 1, end, flag)); } lookup[start][flag] = res; } // return solution to current sub-problem return lookup[start][flag]; } // Function to find length of longest subsequence with alternate // low and high elements. It uses Util() method. int findLongestSequence(int arr[], int n) { // Fix first element and recurse for remaining elements. // There are two possibilities - // 1. Next element is greater (pass true) // 2. Next element is smaller (pass false) return 1 + max(Util(arr, 1, n - 1, true), Util(arr, 1, n - 1, false)); } // main function int main() { int arr[] = { 8, 9, 6, 4, 5, 7, 3, 2, 4 }; int n = sizeof(arr) / sizeof(arr[0]); // Find Longest alternating subsequence cout << "The length of Longest Subsequence is " << findLongestSequence(arr, n); return 0; } |

`Output:`

The length of Longest 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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
class LongestSequence { // Util function to find length of longest subsequence // if flag is true, next element should be greater // if flag is false, next element should be smaller public static int Util(int[] A, int start, int end, int flag, int[][] lookup) { if (start >= A.length) { return 0; } // if sub-problem is seen for the first time, solve it and // store its result in lookup table if (lookup[start][flag] == 0) { int res = 0; for (int i = start; i <= end; i++) { // include A[i] as next high in subsequence and flip flag // for next subsequence if (flag == 1 && A[i - 1] < A[i]) { res = Integer.max(res, 1 + Util(A, i + 1, end, 0, lookup)); } // include A[i] as next low in subsequence and flip flag // for next subsequence else if (flag == 0 && A[i - 1] > A[i]) { res = Integer.max(res, 1 + Util(A, i + 1, end, 1, lookup)); } // don't include A[i] in subsequence else { res = Integer.max(res, Util(A, i + 1, end, flag, lookup)); } } lookup[start][flag] = res; } // return solution to current sub-problem return lookup[start][flag]; } // Function to find length of longest subsequence with alternate // low and high elements. It uses Util() method. public static int findLongestSequence(int[] A, int[][] lookup) { // Fix first element and recurse for remaining elements as first // element will always be part of longest subsequence (why?) // There are two possibilities - // 1. Next element is greater (pass true) // 2. Next element is smaller (pass false) return 1 + Integer.max(Util(A, 1, A.length - 1, 1, lookup), Util(A, 1, A.length - 1, 0, lookup)); } // main function public static void main(String[] args) { int[] A = { 8, 9, 6, 4, 5, 7, 3, 2, 4 }; // lookup table to store solutions of subproblem // max(lookup[i][0], lookup[i][1]) stores longest sequence // till A[0..i] int[][] lookup = new int[A.length][2]; System.out.println("The length of Longest Subsequence is " + findLongestSequence(A, lookup)); } } |

`Output:`

The length of Longest Subsequence is 6

The time complexity of above solution is O(n^{2}) and auxiliary space used by the program is O(n).

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Is any video tutorials available to understand the solution better?

Sorry, we don’t have any as of now.

I don’t understand why the solution needs a for loop, it works fine without it.

Also this dp solution works, O(n) complexity. Maybe I don’t understand something, but no matter what sequence I try, I can’t find a sequence where this solution would return a different result comparing to the solution from the article:

`int altSequenceDp(int arr[], int n) {`

..int lastInc = 1;

..int lastDec = 1;

..for (int i = 1; i < n; i++) {

....if (arr[i] > arr[i - 1]) {

......lastInc = lastDec + 1;

....} else if (arr[i] < arr[i - 1]) {

......lastDec = lastInc + 1;

....}

..}

`..return max(lastInc, lastDec);`

}

Think about this. What if the final element don’t need to be next to each other in its original index. Could you find the longest alternating subsequence?