Java 中所有元素均为偶数或奇数的最大子数组

给定一个包含非负数的数组 inputArr[]。我们的任务是找到一个最长子数组，该子数组中的所有元素要么都是偶数，要么都是奇数。

示例：1

输入

int arr[] = {5, 5, 3, 7, 9, 7, 0, 1, 2, 7}

输出 6

解释：子数组 {5, 5, 3, 7, 9, 7} 是包含所有奇数元素的最长子数组，其长度为 6。

示例：2

输入

int arr[] = {9, 2, 0, 4, 8, 6, 2, 0, 0, 1, 5, 4, 4, 1, 7}

输出 8

解释：子数组 {2, 0, 4, 8, 6, 2, 0, 0} 是包含所有偶数元素的最长子数组，其长度为 8。

朴素方法

基本方法的朴素做法是计算所有子数组，然后检查这些子数组的元素是偶数还是奇数。包含所有奇数或偶数元素且在具有给定条件的子数组中最大的那个就是我们的答案。

步骤 1：创建一个名为 findCountLongestSubArr() 的方法，该方法接受输入数组。

步骤 2：在方法内部，创建嵌套的 for 循环。这些嵌套的 for 循环将计算所有子数组。

步骤 3：使用一个名为 isOdd 的标志，筛选出子数组的奇数或偶数元素，但不能同时筛选。子数组的第一个元素决定了子数组的后续元素是偶数还是奇数。

步骤 4：创建两个变量 countEle 和 ans。变量 countEle 计算子数组中符合条件的元素的数量，而 ans 存储问题的最终答案。

步骤 5：在内层 for 循环中，检查当前元素是否为奇数，以及子数组的第一个元素。如果第一个元素和当前元素都是奇数或都是偶数，则将变量 countEle 增加 1；否则，使用 break 语句终止内层循环。

步骤 6：内层循环终止后，比较 ans 和 countEle 的值。将这两个值中较大的一个存储在变量 ans 中。

步骤 7：最后，返回变量 ans。

实施

请看基于以上步骤的实现。

文件名：LongestSubArr.java

输出

For the input array: 
5 5 3 7 9 7 0 1 2 7 
The length of the largest odd or even subarray is: 6


For the input array: 
9 2 0 4 8 6 2 0 0 1 5 4 4 1 7 
The length of the largest odd or even subarray is: 8

复杂度分析：由于嵌套的 for 循环，程序的 time complexity 为 O(n²)，其中 n 是输入数组中元素的总数。该程序不使用任何数据结构。因此，程序的 space complexity 为常数，即 O(1)。

借助动态规划，我们可以将程序的 time complexity 从 O(n²) 降低。以下方法展示了这一点。

方法：使用动态规划

步骤 1：创建一个数组 dpArr[]，其中 dpArr[p] 表示以索引 p 结尾的子数组的长度。

步骤 2：将 dpArr[0] 赋值为 1。

步骤 3：初始化变量 temp 为 1，用于存储答案。

步骤 4：使用循环遍历输入数组的元素，并在每次迭代中执行以下操作。请注意，迭代应从 (1 到 N) 开始。

• If(inputArr[p] % 2 == inputArr[p - 1] % 2) then dpArr[p] = dpArr[p - 1] + 1
• Else, dpArr[p] = 1

步骤 5：遍历 dpArr[] 并找到最大值。

步骤 6：将（在上一步中找到的）最大值赋给变量 temp。

步骤 7：返回 temp。

请看使用上述步骤实现的实现。

文件名：LongestSubArr1.java

输出

For the input array: 
5 5 3 7 9 7 0 1 2 7 
The length of the largest odd or even subarray is: 6


For the input array: 
9 2 0 4 8 6 2 0 0 1 5 4 4 1 7 
The length of the largest odd or even subarray is: 8

复杂度分析：程序使用了两个 for 循环。但是它们不是嵌套的。因此，程序的 time complexity 为 O(n)。此外，该程序使用了辅助数组（在本例中为 dpArr[]），使程序的 space complexity 为 O(n)，其中 n 是输入数组中元素的总数。

我们在 time complexity 方面进行了优化。但是，这牺牲了辅助数组，使 space complexity 变为 O(n)。现在，我们将进行优化以降低 space complexity。

我们发现 dpArr[p] 仅依赖于 dpArr[p - 1]（参见上面编写的程序）。因此，我们可以说 dpArr[] 的当前元素仅依赖于 dpArr[] 的最后一个元素，因此我们不需要辅助数组。我们只需要一个变量来完成我们的工作。下面对此进行了说明。

文件名：LongestSubArr2.java

输出

For the input array: 
5 5 3 7 9 7 0 1 2 7 
The length of the largest odd or even subarray is: 6


For the input array: 
9 2 0 4 8 6 2 0 0 1 5 4 4 1 7 
The length of the largest odd or even subarray is: 8

复杂度分析：程序的 time complexity 与上一个程序相同。该程序不使用任何数据结构，使程序的 space complexity 为常数，即 O(1)。