Given a sequence of numbers you have to find out the length of the longest increasing odd even subsequence and print the length of the subsequence

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

mahmoud2506

Save to bookmark

2022-05-01

228

Longest Increasing Odd Even Subsequence

Given a sequence of numbers you have to find out the length of the longest increasing odd even subsequence and print the length of the subsequence. The sequence will be maintaining like, (odd ) -> ( even ) -> ( odd ) -> ( even ) or (even ) -> ( odd ) -> ( even ) -> ( odd ) .

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 increasing 
odd even subsequence

Example

T=3

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

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

Input:
7
6 5 9 2 10 77 5

Output:
4 (6 9 10 77 )

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 odd(a) = the value at the index a of the odd array and even(a) = the value at the index a of the even array.

To find the length of the longest increasing odd even subsequence we will follow these steps,

We take two new array one is an odd array and another is even an array and initialize both with 1. We start our algorithm with the second column. We check elements that are before the current element, with the current element.
If the current element is odd and the comparing the element is even then,
odd (index of current element) = even (index of the comparing element) + 1 ;
If the current element is even and the comparing element is odd then,
even (index of current element) = odd (index of the comparing element) + 1;

C++ Implementation:

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

int length_of_subsequence(int* arr, int n)
{
    int a[n];
    for (int i = 0; i < n; i++) {
        a[i] = 1;
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] % 2 == 0) {
                if (arr[j] % 2 == 1 && arr[j] < arr[i]) {
                    a[i] = max(a[i], a[j] + 1);
                }
            }
            else {
                if (arr[j] % 2 == 0 && arr[j] < arr[i]) {
                    a[i] = max(a[i], a[j] + 1);
                }
            }
        }
    }
    int Max = 0;
    for (int i = 0; i < n; i++) {
        Max = max(Max, a[i]);
    }
    cout << endl;
    return Max;
}

int main()
{
    int t;
    
    cout << "TestCase : ";
    cin >> t;
    
    while (t--) {
        int n;
    
        cout << "Enter number of elements : ";
        cin >> n;
    
        int arr[n];
        cout << "Enter the elements : ";
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        cout << "Length of the subsequence : " << length_of_subsequence(arr, n) << endl;
    }
    
    return 0;
}

Output

TestCase : 3
Enter number of elements : 8
Enter the elements : 2 3 4 8 2 5 6 8
Length of the subsequence : 5
Enter number of elements : 8
Enter the elements : 2 3 4 8 2 6 5 4
Length of the subsequence : 4
Enter number of elements : 7
Enter the elements : 6 5 9 2 10 77 5
Length of the subsequence : 4

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

total answers (1)