The problem we are trying to solve is Given an array of size n, we have to find the length of Longest subsequence in the given array such that all the elements of the subsequence are sorted in increasing order and also they are alternately odd and even.

The overall time complexity of our efficient approach will be O(N^2) where N is the number of elements in the given array. We have used Dynamic Programming for this.

Problem

You are given an array of length n.

You have to find the longest increasing subsequence from the given array, such that alternative elements are odd and even.

Given array :
arr = {5,6,2,1,7,4,8,3}

Our output will be 4, as {5,6,7,8} is the longest subsequence having alternate odd and even elements.

Approach

One of the Naive approach to solve this problem could be considering all subsequences with alternate odd even numbers in increasing order. Out of them select the longest one. This has an exponential time complexity and will not be an efficient approach.

As there are O(2^N) subsequences in a list of N numbers, this brute force approach will take exponential time O(2^N) and constant space O(1).

So, our Efficient approach would be to use Dynamic programming to solve this problem.

We store the longest increasing odd-even sub-sequence ending at each index of given arr[]. We create an auxiliary array dp[] such that dp[j] stores length of Longest increasing odd even subsequence or LIOES ending with arr[j]. At the end, we return maximum value from this array.

dp[j] = length of Longest increasing odd even subsequence ending with arr[j]

For filling values in this dp array, we traverse all elements of arr[] and for each element, we traverse all elements of same array till that position and check for our conditions.

If it satisfies all the conditions, we update dp[j] with length of current LIOES.

if (arr[i] > arr[j] and (arr[i]+arr[j]) % 2 != 0 and dp[i] < dp[j] + 1)
    dp[i] = dp[j] + 1

Pseudocode

1. Create a dp table of length same as given array and elements as 1, because each element of given array is a subsequence itself.
2. Start traversing all elements of arr and for each element, traverse all the elements till that position again checking for conditions.
3. If all the conditions are satisfied, that position in dp[] array is incremented.
4. Conditions we check for are : arr[i]>arr[j] and (arr[i] + arr[j]) % 2 != 0 and dp[i] < dp[j] + 1 where, i is iterator of primary loop and j is iterator of secondary loop.
5. After our primery loop is completed, we return thr maximum value of our dp array.

Implementation in Python

# Function that returns answer
def answer(arr):
    
    # Taking length of given array
    l = len(arr)
    
    # Creating the DP table of length l and elements as 1
    dp = [1]*l
    
    # Primary loop
    for i in range(1,n):
    
        # Secondary loop
        for j in range(i):
            
            # Checking for conditions
            if (arr[i] > arr[j] and (arr[i]+arr[j]) % 2 != 0 and dp[i] < dp[j] + 1):
            
                # Incrementing value in dp table
                dp[i] = dp[j] + 1
                
    # Returning maximum value from DP array
    return max(dp)

arr = {5,6,2,1,7,4,8,3}
print('Length of LIOES is :',answer(arr))

Workflow of solution

• Suppose we give our arr1 as [2,7,3,4,9,1] to our answer funtion.
• Length of array is taken in l variable as l = 6.
• An array with elements as 1 and length same as l is declared. Our dp array will look like : [1,1,1,1,1,1]
• We start traversing all elements of arr and for each element, we traverse same array again till that position.
• When we find an element in secondary loop, that is smaller than our current element of primary loop and satisfies the odd-even condition and length of LIOES at that position + 1 is greater that LIOES of current primary loop position than we increment our dp table at that index.
• After traversing on second element of arr, and all elements of same arr till second element, our dp table will look like : [1,2,1,1,1,1] as first element of arr satisfies all the conditions mentioned above, we incremented the our dp table at second position.
• Similarly, for third elements of arr, exact process is repeated, and as first element again satisfies all conditions our dp table would look like : [1,2,2,1,1,1]. Here we incremented our third element of dp array.
• After our primary loop is completed, our dp table would look like : [1,2,2,3,4,1]
• At end, maximum value from this dp table is returned by function as our LIOES=4.

Complexity

• As we traverse all elements of arr twice in a nested loop, our time complexity would be O(n^2), where n is length of array.
• For storing all LIOES for each element of arr, we created an array of size n, so our space complexity would be O(n).

With this article at OpenGenus, you will have the complete idea of solving the problem of finding the Longest Increasing Odd Even Subsequence using Dynamic Programming. Enjoy.