# Longest alternating subsequence

A sequence {x1, x2, .. xn} is alternating sequence if its elements satisfy one of the following relations :

x1 < x2 > x3 < x4 > x5 < …. xn or x1 > x2 < x3 > x4 < x5 > …. xn

Examples:

Input: arr[] = {1, 5, 4} Output: 3 The whole arrays is of the form x1 < x2 > x3 Input: arr[] = {1, 4, 5} Output: 2 All subsequences of length 2 are either of the form x1 < x2; or x1 > x2 Input: arr[] = {10, 22, 9, 33, 49, 50, 31, 60} Output: 6 The subsequences {10, 22, 9, 33, 31, 60} or {10, 22, 9, 49, 31, 60} or {10, 22, 9, 50, 31, 60} are longest subsequence of length 6.

Below is recursive structure in the problem.

lookup[i][0] = Length of the longest Zig-Zag subsequence ending at index i and last element is greater than its previous element lookup[i][1] = Length of the longest Zig-Zag subsequence ending at index i and last element is smaller than its previous element Recursive Formulation: lookup[i][0] = max (lookup[i][0], lookup[j][1] + 1); for all j < i and arr[j] < arr[i] lookup[i][1] = max (lookup[i][1], lookup[j][0] + 1); for all j < i and arr[j] > arr[i]

In this post, a memoization based solution is discussed.

// C++ program to find length of the longest // alternating subsequence. #include <bits/stdc++.h> 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 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 already solved if (lookup[start][flag] != 0) return lookup[start][flag]; // if sub-problem is seen for the first time, // solve it and store its result in lookup table 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]); cout << findLongestSequence(arr, n); return 0; }

Output:

6

Time complexity : O(n^{2})

Auxiliary Space : O(n)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below

source and credits.

source and credits:http://www.geeksforgeeks.org/longest-alternating-subsequence/

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon

If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements

#technicalguide