Home » Interview coding problems/challenges

Longest alternating subsequence

Longest alternating subsequence: Here, we are going to learn how to find the longest alternating subsequence from given a sequence of numbers using the dynamic programming approach?
Submitted by Souvik Saha, on June 26, 2020

Problem statement

Given a sequence of numbers you have to find out the longest alternating subsequence and print the length of the subsequence. A sequence is an alternating sequence when it will be maintain like (increasing) -> (decreasing) -> (increasing) -> (decreasing) or (decreasing) -> (increasing) -> (decreasing) -> (increasing).

Input:
T Test case
T no. of input array along with their element no. N

E.g.
3

8
2 3 4 8 2 5 6 8
8
2 3 4 8 2 6 5 4
7
6 5 9 2 10 77 5

Constrain:
1≤ T ≤ 20
1≤ N ≤50
1≤ A[i] ≤50

Output:
Print the length of the longest alternating subsequence.

Example

T=3

Input:	
8
2 3 4 8 2 5 6 8 

Output:
4 (4, 8, 2, 5)

Input:
8
2 3 4 8 2 6 5 4

Output:
5 ( 4, 8, 2, 6, 4 )

Input:		
7
6 5 9 2 10 77 5

Output:
6 (6, 5, 9, 2, 10, 5 )

Explanation with example

Let N be the number of elements say, X₁, X₂, X_3, ..., X_n

Let up(a) = the value at the index a of the increasing array and down(a) = the value at the index a of the decreasing array

To find out the length of the longest alternating sequence we will follow these steps,

1. We take two new array one is an increasing array and another is decreasing array and initialize it with 1. We start our algorithm with the second column. We check elements that are before the current element, with the current element.
2. If any element is less than the current element then,
   up (index of current element) = down (index of the comparing element) + 1;
3. If the element is greater than the current element then, down
   (index of current element) = up (index of the comparing element) + 1;

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int find_length(int* arr, int n)
{
    int up[n];
    int down[n];

    for (int i = 0; i < n; i++) {
        up[i] = 1;
        down[i] = 1;
    }

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                up[i] = max(up[i], down[j] + 1);
            }
            else if (arr[i] < arr[j]) {
                down[i] = max(down[i], up[j] + 1);
            }
        }
    }

    int m = 0;

    for (int i = 0; i < n; i++) {
        m = max(m, max(up[i], down[i]));
    }

    return m;
}

int main()
{
    //code
    int t;

    cout << "Testcase : ";
    cin >> t;

    while (t--) {
        int n;

        cout << "Enter the element number : ";
        cin >> n;

        int arr[n];

        cout << "Fill the array : ";
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }

        cout << "Length of the subsequence : " << find_length(arr, n) << endl;
    }

    return 0;
}

Output

Testcase : 3
Enter the element number : 8
Fill the array : 2 3 4 8 2 5 6 8	
Length of the subsequence : 4
Enter the element number : 8
Fill the array : 2 3 4 8 2 6 5 4
Length of the subsequence : 5
Enter the element number : 7
Fill the array : 6 5 9 2 10 77 5
Length of the subsequence : 6