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, 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,

  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





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.