Longest Alternating Subsequence

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:

1. Let a be an array of size n.
2. 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.
3. Initialize all sublen[][] values to 1. Since, the smallest possible alternating subsequence is 1.
4. 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:

1. 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.
2. Let us take two variables:
   • legtp : Length of longest alternating subsequence with last element greater than previous element.
   • lestp : Length of longest alternating subsequence with last element smaller than previous element.
3. We initialize legtp and lestp with 1, since that's the smallest possible subsequence if the array is not empty.
4. 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
5. 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).