Java 中最长奇偶子序列

2024 年 9 月 10 日 | 阅读 7 分钟

Java 中最长奇偶子序列是一个问题，需要在一个大小为 s 的非负数组中找到一个子序列，该子序列以交替的方式包含奇偶数。因此，需要找到具有交替奇偶数序列的最长子序列中的元素数量。请注意，子序列可以以偶数或奇数开头。让我们通过一些例子来理解它。

例如

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

输出 8

解释: 所需的最长子序列是 (15, 16, 19, 14, 17, 18, 21, 30) 或 (15, 16, 19, 14, 17, 18, 21, 78)，子序列中的元素数量为 8。

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

输出 7

解释: 所需的最长子序列是 (11, 112, 15, 130, 131, 140, 117) 或 (11, 112, 15, 130, 131, 140, 111)，或者可能还有其他子序列，子序列中的元素数量为 7。

方法

有两种方法可以找出最长的奇偶子序列。一种是暴力法，也称为朴素法。另一种是使用动态规划的高效方法。让我们从朴素法开始。

朴素方法

在这种方法中，我们将找出给定数组的所有可能子序列。然后，对于所有计算出的子序列，我们将过滤出最长的奇偶子序列。为了更好地理解，请观察以下程序。

文件名: OddEvenSeq.java

// importing Array List
import java.util.ArrayList;

public class OddEvenSeq
{
public ArrayList<Integer> al;
public ArrayList<ArrayList<Integer>> al2;

// constructor of the class
OddEvenSeq()
{
// initializing the 1-d and 2-d array list
al = new ArrayList<Integer>();
al2 = new ArrayList<ArrayList<Integer>>();

}

// a method that finds out all of the subsequences
// of the input array a of the size s
public void findSubSequence(int a[], int i, int s, ArrayList<ArrayList<Integer>> store)
{
// handling the base case
if(i >= s)
{
ArrayList<Integer> temp = new ArrayList<Integer>();

for(int j = 0; j < al.size(); j++)
{
temp.add(al.get(j));
}
// storing the array list temp in the store
// temp is a subsequence of the input array a[]
store.add(temp);
return;
}

// recursively computing all of the subsequences
// there could be only two cases: one is to include
// the element and other is to exclude the element

al.add(a[i]); // including the element


// after adding the element recur to the 
// next element
findSubSequence(a, i + 1, s, store);
if(al.size() > 0)
{
// excluding the element
al.remove(al.size() - 1);

}

// after removing the element recur for the next element
findSubSequence(a, i + 1, s, store);

}

// a method that finds out the count of elements
// present in the longest subsequence
public int longestSubSequenceCount()
{
int s1 = al2.size();
int count = 0;
int ans = 0;
for(int i = 0; i < s1; i++)
{
// resetting the count to 0
// for the next iteration
count = 0;

// taking one of the array list
// present in the 2-d array list
ArrayList<Integer> temp = al2.get(i);
int s2 = temp.size();

// it is find that keeps track of 
// whether the next element should be odd or even
// find has only two values or states 0 & 1
// 0 means even state and 1 means odd state
int find = -1;
for(int j = 0; j < s2; j++)
{
int num = temp.get(j);
if(find == -1)
{

if((num & 1) == 1)
{
// the current element is odd
// hence the value of find is 1
find = 1;
}
else
{
// the current element is even
// hence the value of find is 0
find = 0;
}

count = count + 1;
ans = Math.max(ans, count);

// if the current element is odd
// the next element has to be even and vice versa
// therefore, we need to toggle the find.
// the following statement does the same
find = 1 - find;
}

else if((num & 1) == find)
{
// control reaching here means
// the current element matches
// the state of find, i.e., if the 
// current element is odd then find is 1
// and if the current element is even then 
// find is 0
count = count + 1;

// again toggle
find = 1 - find;
ans = Math.max(ans, count);
}

// if the state of find does not 
// match with the state of the current 
// element, then terminate the loop
else
{

break;
}
}
}

return ans;
}

// main method
public static void main(String argvs[])
{
//creating an object of the class OddEvenSeq
OddEvenSeq obj = new OddEvenSeq();

// input array
int a[] = {15, 16, 19, 14, 17, 18, 21, 30, 78};
int size = a.length;
obj.findSubSequence(a, 0, size, obj.al2);
System.out.println("For the input array: ");
for(int i = 0; i < size; i++)
{
System.out.print(a[i] + " ");    
}
System.out.println("\n");

int ans = obj.longestSubSequenceCount();

System.out.println("The longest odd even subsequence is: " + ans); 

// clearing the array lists
obj.al2.clear();
obj.al.clear();

// another input array
int a1[] = {11, 112, 12, 122, 15, 130, 131, 140, 117, 111};
size = a1.length;
System.out.println();

obj.findSubSequence(a1, 0, size, obj.al2);
System.out.println("For the input array: ");
for(int i = 0; i < size; i++)
{
System.out.print(a1[i] + " ");    
}
System.out.println("\n");

ans = obj.longestSubSequenceCount();

System.out.println("The longest odd even subsequence is: " + ans);


}
}

输出

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

复杂度分析: 在上述程序中，有两个选择；一个是包含该元素，另一个是排除该元素。因此，该程序的时间复杂度是指数级的，即 O(2ⁿ)，其中 n 是数组中存在的元素总数。时间复杂度 O(2ⁿ) 非常大。因此，对于包含大量元素的输入数组，上述程序不适用。此外，程序占用了大量额外的空间，这也是指数级的 O(2ⁿ)。

实现：动态规划

设 longLen(j) 为以索引 j 结尾的最长奇偶子序列 (LOES) 的长度，使得 a[j] 是 LOES 的最后一个元素。因此，longLen(j) 可以递归地写为：longLen(j) = 1 + max(longLen(i))，其中 0 < i < j 且 (a[i] < a[j]) 且 (a[i]+a[j]) % 2 != 0；或者 longLen(j) = 1，如果不存在这样的 i。为了计算给定数组的最长奇偶子序列，需要返回 max(longLen(j))，其中 0 < j < size。

以下程序实现了上述递归关系中的动态规划方法。

文件名: OddEvenSeq1.java

public class OddEvenSeq1
{

    public int longOddEvenSeq(int a[], int size)
    {
        // loes[j] keeps the longest odd even
        // subsequence which is ending at a[j]
        int[] loes = new int[size];
 
        // to keep the size of the longest odd
        // even subsequence
        int maximumLen = 0;
 
        // Initialize LOES values for all indexes
        for (int j = 0; j < size; j++)
        {
            loes[j] = 1;
        }
 
        // Computing the optimized LOES values
        // in the bottom up manner
        for (int j = 1; j < size; j++)
        {
            for (int i = 0; i < j; i++)
            {
                // in an alternating sequence of odd and even numbers
                // the sum of any two numbers, where one is odd and other is even
                // is always odd
                if ((a[j] + a[i]) % 2 != 0 && loes[j] < loes[i] + 1)
                {
                    loes[j] = loes[i] + 1;
                }
            }
        }
 
        // Picking the maximum of all the LOES values
        for (int k = 0; k < size; k++)
        {
            if (maximumLen < loes[k])
            {
                maximumLen = loes[k];
            }
        }
 
        // returning the maximum length
        return maximumLen;
    }


// main method
public static void main(String argvs[])
{
//creating an object of the class OddEvenSeq1
OddEvenSeq1 obj = new OddEvenSeq1();

int a[] = {15, 16, 19, 14, 17, 18, 21, 30, 78};
int size = a.length;

System.out.println("For the input array: ");
for(int i = 0; i < size; i++)
{
System.out.print(a[i] + " ");    
}
System.out.println("\n");

int ans = obj.longOddEvenSeq(a, size);

System.out.println("The longest odd even subsequence is: " + ans); 



}
}

输出

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

The longest odd even subsequence is: 8

复杂度分析: 上述程序使用了 2 级嵌套的 for 循环。因此，该程序的时间复杂度为 O(n²)，其中 n 是数组中存在的元素总数。该程序使用数组作为额外的内存，大小为 n。因此，该程序的空间复杂度为 O(n)。

下一个主题Java 计算当前日期减去几天

Java 中最长奇偶子序列

方法

朴素方法

实现：动态规划

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中最长奇偶子序列

方法

朴素方法

实现：动态规划

相关帖子

如何在 Java 中接受日期

Difference Between C, C++, and Java

Program to Accept String Starting With Capital Letter in Java

Permutation of Numbers in Java

Java Vector 操作

How to Calculate Date Difference in Java

Java 中的 FloatBuffer put() 方法及示例

如何在 Java 中使字段可序列化

Java 并发中 Lock 和 Monitor 的区别

Java 中的 Manacher 算法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器