Home » Interview coding problems/challenges

Longest Increasing Odd Even Subsequence

Longest Increasing Odd-Even Subsequence: This a standard interview preparation problem to find the length of the longest increasing odd-even subsequence using Dynamic programming.
Submitted by Souvik Saha, on June 29, 2020

Problem statement

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 )

Explanation with example

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

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,

1. 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.
2. 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 ;
3. 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