# 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 (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(n2)
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