Q:

# 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 )```

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