# Longest Alternating Subsequence

Get this book -> Problems on Array: For Interviews and Competitive Programming

**What is an alternating sequence?**

A sequence a1, a2, a3,... an is called alternating if it follows any one of the conditions given below.

```
a1 < a2 > a3 < ... an
-OR-
a1 > a2 < a3 > ... an
```

**What is a subsequence?**

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

### The Problem

Given an array, find the length of the longest alternating subsequence.

### Example 1

```
Input:
5 10 7 22
Output:
4
Explanation:
5 < 10 > 7 < 22
```

### Example 2

```
Input:
11 4 26 14 29
Output:
5
Explanation:
11 > 4 < 26 > 14 < 29
```

### Example 3

```
Input:
3 5 6 4
Output:
3
Explanation:
3 < 5 > 4
-OR-
3 < 6 > 4
```

We solve this using two approaches:

- Dynamic Programming O(N^2) time
- Efficient Approach O(N) time

## Approach (Dynamic Programming)

The steps to find the Longest Alternating Subsequence are:

- Let a be an array of size n.
- We define a 2D array sublen[n][2] such that sublen[i][0] contains longest alternating subsequence ending at index i and last element is greater than its previous element and sublen[i][1] contains longest alternating subsequence ending at index i and last element is smaller than its previous element.
- Initialize all sublen[][] values to 1. Since, the smallest possible alternating subsequence is 1.
- Then, loop through the array and find the sublen[][] values using the following recurrence relation.

```
sublen[i][0] = max (sublen[i][0], sublen[j][1] + 1);
for all j < i and a[j] < a[i]
sublen[i][1] = max (sublen[i][1], sublen[j][0] + 1);
for all j < i and a[j] > a[i]
```

Instead of explaining the approach with an example, it would be better to take a look at the program and trying yourself to trace it!

### Solution

C++

```
#include<iostream>
using namespace std;
// Function to return max of two numbers
int max(int a, int b)
{
return (a > b) ? a : b;
}
// Function to return longest alternating
// subsequence length
int LongestAlterSub(int arr[], int n)
{
/*sublen[i][0] = Length of the longest
alternating subsequence ending at
index i and last element is greater
than its previous element
sublen[i][1] = Length of the longest
alternating subsequence ending
at index i and last element is
smaller than its previous element */
int sublen[n][2];
// Initialize all values from 1
for(int i = 0; i < n; i++)
sublen[i][0] = sublen[i][1] = 1;
// Initialize result
int res = 1;
// Compute values in bottom up manner
for(int i = 1; i < n; i++)
{
// Consider all elements as
// previous of arr[i]
for(int j = 0; j < i; j++)
{
// If arr[i] is greater, then
// check with las[j][1]
if (arr[j] < arr[i] &&
sublen[i][0] < sublen[j][1] + 1)
sublen[i][0] = sublen[j][1] + 1;
// If arr[i] is smaller, then
// check with las[j][0]
if(arr[j] > arr[i] &&
sublen[i][1] < sublen[j][0] + 1)
sublen[i][1] = sublen[j][0] + 1;
}
// Pick maximum of both values at index i
if (res < max(sublen[i][0], sublen[i][1]))
res = max(sublen[i][0], sublen[i][1]);
}
return res;
}
// Driver Code
int main()
{
//size of array
int n;
cin >> n;
//read the array
int arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
//function call
cout << LongestAlterSub(arr, n) << endl;
return 0;
}
```

**Time Complexity:** Since, two loops are involved the time complexity is O(n^2).

**Space Complexity:** Since, an auxiliary array is used, the space complexity is O(n).

## Approach (Easy and Efficient)

Following are the steps to find Longest Alternating Subsequence efficiently:

- As you can see from the definition and examples, there are two possible patterns of alternating subsequences:
- The last element is
**greater**than the previous element. - The last element is
**smaller**than the previous element.

- The last element is
- Let us take two variables:
**legtp**: Length of longest alternating subsequence with**l**ast**e**lement**g**reater**t**han**p**revious element.**lestp**: Length of longest alternating subsequence with**l**ast**e**lement**s**maller**t**han**p**revious element.

- We initialize
**legtp**and**lestp**with 1, since that's the smallest possible subsequence if the array is not empty. - We loop through the array and,
- if we find an element greater than the previous element, we set

**legtp = lestp + 1** - if we find an element smaller than the previous element, we set

**lestp = legtp + 1**

- if we find an element greater than the previous element, we set
- Finally, the maximum of
**legtp**and**lestp**is our answer.

Let's take an example to understand the approach.

### Example 4

```
Input:
a[] = 10 5 6 7 8
Approach:
legtp = 1
lestp = 1
At i = 1,
a[i] = 5
a[i - 1] = 10
5 < 10
lestp = legtp + 1
lestp = 1 + 1 = 2
At i = 2,
a[i] = 6
a[i - 1] = 5
6 > 5
legtp = lestp + 1
legtp = 2 + 1 = 3
At i = 3,
a[i] = 7
a[i - 1] = 6
7 > 6
legtp = lestp + 1
legtp = 2 + 1 = 3
At i = 4,
a[i] = 8
a[i - 1] = 7
8 > 7
legtp = lestp + 1
legtp = 2 + 1 = 3
Output:
3
The sequences can be:
10 > 5 < 6
10 > 5 < 7
10 > 5 < 8
```

### Solution

C++

```
#include <bits/stdc++.h>
using namespace std;
int LongestAlterSub(int arr[], int n)
{
// "legtp" and "lestp" intialized as 1
int legtp = 1;
int lestp = 1;
// Loop from the second element
for (int i = 1; i < n; i++)
{
if (arr[i] > arr[i - 1])
{
legtp = lestp + 1;
}
else if (arr[i] < arr[i - 1])
{
lestp = legtp + 1;
}
}
return max(legtp, lestp);
}
// Driver Code
int main()
{
//size of array
int n;
cin >> n;
//read the array
int arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
//function call
cout << LongestAlterSub(arr, n) << endl;
return 0;
}
```

**Time Complexity:** Since, only one loop is involved the time complexity is O(n).

**Space Complexity:** Since, no extra space is used, the space complexity is O(1).