Longest Odd Even Subsequence in Java
In order to solve the Java problem known as the longest odd-even subsequence, one must identify a sequences in a non-negative array having size s that alternately includes odd and even values. In order to determine the number of numbers with in longest subsequence that includes an alternate sequence of odd and even numbers, one must count the number of numbers in the subsequence. The subsequence may begin with either an even or an odd integer. With the aid of several instances, let's comprehend it.
For instance:
Input: int arr[] = {13, 18, 23, 20, 29, 16, 17, 34, 61, 70}, //length l = 9
Output: 8
Explanation: The necessary maximum subsequence set is (13, 18, 23, 20, 29, 16, 17, 34, 61, 70, with an element count of 8.
Input: int arr[] = {9, 110, 10, 120, 13, 128, 127, 138, 115, 109}, //Length l = 10
Output: 7
Explanation: The needed largest subsequence set is (9, 110, 10, 120, 13, 128, 127, 138, 115, 109) or (9, 110, 10, 120, 13, 128, 127, 138, 115, 109), however another subsequence may also exist, and the subsequence's element count is 7.
Approaches
To determine the longest odd-even subsequence, there are two methods. One is called the brute force strategy, commonly referred to as the naive strategy. The effective strategy of dynamic programming is the alternative. Start with the simple-minded person.
Unfavour Approach
With this method, we will identify every subsequence of the supplied array. The largest odd-even subsequence will then be filtered out for all calculated subsequences. Watch the following show for a better understanding.
Let the name of the file is OddEvenSeqDemo.java
// importing an Array List
import java.util.ArrList;
public class OddEvenSeqDemo
{
public ArrList<Integer> sr;
public ArrList<ArrList<Integer>> sr2;
// class constructor
OddEvenSeqDemo()
{
// setting up the 1- and 2-dimensional array lists
sr = new ArrList<Integer>();
sr2 = new ArrList<ArrList<Integer>>();
}
// a technique that identifies every
// subsequence of input array an of size h
public void findSubSeq(int b[], int k, int h, ArrList<ArrList<Integer>> store)
{
// addressing the default case
if(k >= h)
{
ArrList<Integer> tempa = new ArrList<Integer>();
for(int l = 0; l < sr.size(); l++)
{
tempa.add(sr.get(l));
}
// The input array a[] is such a subset of the array list temp,
// which is stored in the store.
store.add(tempa);
return;
}
// calculating each subsequence recursively
// There could only be two possibilities:
// either include the element or omit it.
sr.add(b[k]); // adding the component
// Recur to the
// next element after inserting the element.
findSubSeq(b, k + 1, h, store);
if(sr.size() > 0)
{
// leaving out the element
sr.remove(sr.size() - 1);
}
// Recur for the following element after eliminating the previous one.
findSubSeq(b, k + 1, h, store);
}
// a technique that counts the number of elements
// inside the longest subsequence
public int longSubSeqCoun()
{
int h1 = sr2.size();
int coun = 0;
int answ = 0;
for(int k = 0; k < h1; k++)
{
// For the subsequent cycle,
// the count will be reset to 0.
count = 0;
// selecting a single array list
// element as from 2-d array list
ArrList<Integer> tempa = sr2.get(k);
int h2 = tempa.size();
// Keeping track of whether the following component
// must be odd or even represents a discovery.
// There are merely values or states for find. 0 & 1
// The state codes are 0 for even and 1 for odd.
int locate = -1;
for(int l = 0; l < h2; l++)
{
int numb = tempa.get(l);
if(locate == -1)
{
if((numb & 1) == 1)
{
// The present element is strange.
// that value for find is 1 as a result.
locate = 1;
}
else
{
// This element is even at this time.
// hence, find's value is 0
locate = 0;
}
coun = coun + 1;
answ = Math.max(answ, coun);
// We need to toggle the find since the next element
// must be even though the present compoent is odd,
// and vice versa. The following phrase
// does the same thing.
locate = 1 - locate;
}
else if((numb & 1) == locate)
{
// If control reaches this point, it signifies that the
// current element fits the current condition of the search, that is, if the
// If the current element is odd, the result is 1.
// and in the event that current element is even, is 0
coun = coun + 1;
// again switch
locate = 1 - locate;
answ = Math.max(answ, coun);
}
// If the current element's state does
// not match the state of find,
// the loop should be terminated.
else
{
break;
}
}
}
return answ;
}
// It is the main method
public static void main(String argvs[])
{
// making a class object of OddEvenSeqDemo
OddEvenSeqDemo pp = new OddEvenSeqDemo();
// input set
int b[] = {17, 18, 21, 16, 19, 20, 23, 3, 28, 31};
int size = b.len;
obj.findSubSeq(b, 0, size, pp.sr2);
System.out.println("To the input array: ");
for(int k = 0; k < size; k++)
{
System.out.print(b[k] + " ");
}
System.out.println("\n");
int answ = pp.longestSubSeqCoun();
System.out.println("The longest sequence that is odd and even is: " + answ);
// getting rid of the array listings
pp.sr2.clear();
pp.sr.clear();
// A second input matrix
int b1[] = {13, 110, 14, 124, 17, 128, 133, 138, 119, 113};
size = b1.length;
System.out.println();
pp.findSubSeq(b1, 0, size, opp.sr2);
System.out.println("To the input array: ");
for(int k = 0; k < size; k++)
{
System.out.print(b1[k] + " ");
}
System.out.println("\n");
answ = pp.longestSubSeqCoun();
System.out.println("The longest sequence that is odd and even is: " + answ);
}
} Output:
To the input array:
17 18 21 16 19 20 23 3 28 31
The longest sequence that is odd and even is: 8
To the input array:
13 110 14 124 17 128 133 138 119 113
The longest sequence that is odd and even is: 7
Analysis of Complexity: There are two options available in the aforementioned programme: either include the piece or exclude it. With n being its total number of items in the array, the preceding program's time complexity is exponential, or O(2n). O(2n) is a very large value for temporal complexity. As a result, the input array with many entries is not a good candidate for the aforementioned application. A significant amount of additional space is also being consumed by the software, which is exponential O(2n).
Implementation of the Dynamic Programming
A[j] is the last element of a Longest Odd-Even Subsequence (LOES), so let lonLen(l) be only the length of the LOES that ends at the index j. LongLen(j) may therefore been written recursively as lonLen(l) = 1 + max(lonLen(k)), where 0 I jl (a[k] a[l]), and (a[k]+a[l])% 2!= 0, or lonLen(l) = 1 if no such I exists. It is necessary to return the max(lonLen(l)), where 0 j size, in order to calculate a longest odd even subsets for the supplied array.
The dynamic programming strategy is used to the aforementioned recursive relation in the programme that follows.
OddEvenSeq3Demo.java
public class OddEvenSeq3Demo
{
public int longOddEvenSeq3Demo(int b[], int size)
{
// The longest odd-even subsequence, which
// ends at b[l], is maintained by loeseq[l].
int[] loeseq = new int[size];
// to maintain the length of the
// longest even/odd sequence
int maxLen = 0;
// Set all indices' LOESEQ values to zero.
for (int l = 0; l < size; l++)
{
loeseq[l] = 1;
}
// Using a bottom-up approach,
// computing the optimum LOESEQ values
for (int l = 1; l < size; l++)
{
for (int k = 0; k < l; k++)
{
// in a pattern of alternate even and odd numbers
// Any two integers that are the sum of one odd number and one even number
// is never normal
if ((b[l] + b[k]) % 2 != 0 && loeseq[l] < loes[k] + 1)
{
loeseq[l] = loeseq[k] + 1;
}
}
}
// choose the highest value among all of the LOESEQ values
for (int m = 0; m < size; m++)
{
if (maxLen < loeseq[m])
{
maxLen = loeseq[m];
}
}
// provide the longest possible length
return maxLen;
}
// It is the main method
public static void main(String argvs[])
{
// making a class object of OddEvenSeq3Demo
OddEvenSeq3Demo pp = new OddEvenSeq3Demo();
int a[] = {17, 18, 21, 16, 19, 20, 23, 28,60};
int size = b.len;
System.out.println("to the input array: ");
for(int k = 0; k < size; k++)
{
System.out.print(b[k] + " ");
}
System.out.println("\n");
int answ = pp.longOddEvenSeqDemo(b, size);
System.out.println("The longest sequence that is odd and even is: " + answ);
}
} Output:
to the input array:
17, 18, 21, 16, 19, 20, 23, 28,60
The longest odd even subsequence is: 8
Analysis of the complexity: The above program uses the 2-level nesting of the for-loops. Therefore, the time complexity of the above program is O(n2), 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).