Home » Interview coding problems/challenges

Print the longest alternating subsequence

Here, we are going to learn the solution to print the longest alternating subsequence using dynamic programming?
Submitted by Souvik Saha, on June 28, 2020

Problem statement

Given a sequence of numbers you have to print the longest alternating subsequence. A sequence is an alternating sequence when it will be maintaining 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 longest alternating subsequence.

Example

T=3

Input:
8
2 3 4 8 2 5 6 8 
Output:
4 8 2 5

Input:
8
2 3 4 8 2 6 5 4
Output:
4 8 2 6 4 

Input:
7
6 5 9 2 10 77 5
Output:
6 5 9 2 10 5 

Explanation with example:

Let N be the number of elements say, X₁, X₂, X₃, ..., 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.
4. After that, we traverse the two arrays and take the maximum value.

Length of the subsequence= max (up(i), down(i))

To print the longest increasing odd-even subsequence, we will follow these steps,

1. We find out the index where the max value contains.
2. If the element at that index is in up array then we traverse the down array where the value difference is one.
3. If the element at that index is in down the array then we traverse the up array where the value difference is one.
4. Follow step 2 and 3 until the value will be 1.

C++ Implementation

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

void print_subsequence(int* arr, int* up, int* down, int n, int m, int ind)
{
    int f_up = 0;
    int f_down = 0;
    vector<int> v;

    if (m == up[ind]) {
        f_up = 1;
    }
    else {
        f_down = 1;
    }

    v.push_back(arr[ind]);
    for (int i = ind - 1; i >= 0; i--) {
        if (m == 1) {
            break;
        }
        if (f_down) {
            if (up[i] + 1 == m) {
                v.push_back(arr[i]);
                m = up[i];
                f_down = 0;
                f_up = 1;
            }
        }
        else if (f_up) {
            if (down[i] + 1 == m) {
                v.push_back(arr[i]);
                m = down[i];
                f_down = 1;
                f_up = 0;
            }
        }
    }
    for (int i = v.size() - 1; i >= 0; i--) {
        cout << v[i] << " ";
    }
    cout << endl;
}

void 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;
    int ind = 0;

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

    print_subsequence(arr, up, down, n, m, ind);
}

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);
    }
    
    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 8 2 5 
Enter the element number : 8
Fill the array : 2 3 4 8 2 6 5 4
Length of the subsequence : 4 8 2 6 5 
Enter the element number : 7              
Fill the array : 6 5 9 2 10 77 5
Length of the subsequence : 6 5 9 2 77 5