Longest Odd-Even Subsequence in Java

10 Sept 2024 | 7 min read

The longest odd-even subsequence in Java is a problem in which one has to find a subsequence in a non-negative array of size s, such that the subsequence contains alternate odd and even numbers in an alternate manner. Thus, one has to find the count of numbers present in the longest subsequence that has the alternative sequence of the odd and even numbers. Note that the subsequence can start either with an even or with an odd number. Let's understand it with the help of some examples.

For example:

Input: int arr[] = {15, 16, 19, 14, 17, 18, 21, 30, 78}, //Size s = 9

Output: 8

Explanation: The required longest subsequence is (15, 16, 19, 14, 17, 18, 21, 30) or (15, 16, 19, 14, 17, 18, 21, 78), and the count of element in the subsequence is 8.

Input: int arr[] = {11, 112, 12, 122, 15, 130, 131, 140, 117, 111}, //Size s = 10

Output: 7

Explanation: The required longest subsequence is (11, 112, 15, 130, 131, 140, 117) or (11, 112, 15, 130, 131, 140, 111), or there can be another subsequence too, and the count of the elements in the subsequence is 7.

Approach

There are two approaches to find out the longest odd-even subsequence. One is the brute force approach, also known as the naïve approach. The other is the efficient approach using dynamic programming. Let's start with the naïve one.

Naïve Approach

In this approach, we will find out the all-possible subsequences of the given array. Then, for all the computed subsequences, we will filter out the longest odd-even subsequence. For better understanding, observe the following program.

FileName: OddEvenSeq.java

Output:

For the input array: 
15 16 19 14 17 18 21 30 78 

The longest odd even subsequence is: 8

For the input array: 
11 112 12 122 15 130 131 140 117 111 

The longest odd even subsequence is: 7

Complexity Analysis: In the above program, there are two choices; one is to include the element, and the other is to exclude the element. Therefore, the time complexity of the above program is exponential, which is O(2ⁿ), where n is the total number of elements present in the array. The time complexity O(2ⁿ) is quite huge. Therefore, the above program is not suitable for the input array that contains a lot of elements. Also, the program is taking a lot of extra space, which is also exponential O(2ⁿ).

Implementation: Dynamic Programming

Let longLen(j) be the length of the Longest Odd-Even Subsequence (LOES) that is ending at the index j so that the a[j] is the last element of the LOES. Thus, longLen(j) can be written recursively as: longLen(j) = 1 + max(longLen(i)), where 0 < i < j and (a[i] < a[j]) and (a[i]+a[j]) % 2 != 0; or longLen(j) = 1, if there is no such i exists. In order to compute the longest odd even subsequence for the given array, it is required to return the max(longLen(j)) where 0 < j < size.

The following program implements the dynamic programming approach for the above-mentioned recursive relation.

FileName: OddEvenSeq1.java

Output:

For the input array: 
15 16 19 14 17 18 21 30 78 

The longest odd even subsequence is: 8

Complexity Analysis: The above program uses the 2-level nesting of the for-loops. Therefore, the time complexity of the above program is O(n²), where n is the total number of elements present in the array. The program is taking an array as the extra memory, which is of the size n. Therefore, the space complexity of the above program is O(n).

Next TopicJava Subtract Days from Current Date

← prev next →