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)

belongs to collection: interview C++ coding problems/challenges | dynamic programming

mahmoud2506

Save to bookmark

2022-05-01

263

Print the longest alternating subsequence

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

C++ programming, Interview questions, C++ programming Interview-questions,

All Answers

mahmoud2506

2022-05-01

need an explanation for this answer? contact us directly to get an explanation for this answer

Let N be the number of elements say, X1, X2, X3, ..., Xn

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,

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.
If any element is less than the current element then,
up( index of current element)= down(index of the comparing element) + 1.
If the element is greater than the current element then,
down( index of current element)= up(index of the comparing element) + 1.
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,

We find out the index where the max value contains.
If the element at that index is in up array then we traverse the down array where the value difference is one.
If the element at that index is in down the array then we traverse the up array where the value difference is one.
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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)