在算法面试中，子序列相关问题一直是热门考点，这类问题往往需要我们在保持元素相对顺序的前提下，找到满足特定条件的最优解。今天我们来深入探讨一道有趣的子序列问题：如何找出数组中最长的有效子序列，其中有效子序列的定义是任意相邻两个元素的和对 2 取模的结果都相同。
首先，让我们明确问题的具体要求：
给定一个整数数组 nums，我们需要找到其最长的有效子序列。有效子序列的定义是：
对于子序列 sub 中的所有相邻元素对 (sub [i], sub [i+1])，它们的和对 2 取模的结果都相同，即 (sub [0] + sub [1]) % 2 == (sub [1] + sub [2]) % 2 == ... == (sub [x-2] + sub [x-1]) % 2。
这里的子序列指的是从原数组中删除一些元素（也可以不删除任何元素）后，剩余元素保持原有顺序组成的新数组。
关键特征分析
要解决这个问题，我们首先需要深入理解有效子序列的数学特征。让我们从相邻元素和的奇偶性入手分析：
两个整数的和对 2 取模的结果只有两种可能：0（偶数）或 1（奇数）。这取决于两个数的奇偶性：
- 当两个数都是奇数时，它们的和是偶数（(奇 + 奇) % 2 = 0）
- 当两个数都是偶数时，它们的和是偶数（(偶 + 偶) % 2 = 0）
- 当一个是奇数一个是偶数时，它们的和是奇数（(奇 + 偶) % 2 = 1 或 (偶 + 奇) % 2 = 1）
这意味着，有效子序列中的所有相邻元素对必须满足以下两个条件之一：
- 所有相邻元素对的和都是偶数（即每对元素同为奇数或同为偶数）
- 所有相邻元素对的和都是奇数（即每对元素一奇一偶）
基于这个发现，我们可以进一步推导有效子序列的整体结构特征。
情况 1：相邻元素和全为偶数（模为 0）
在这种情况下，每对相邻元素必须同为奇数或同为偶数。这可能产生两种子序列：
- 全奇数子序列：所有元素都是奇数，任意两个相邻元素的和为偶数
- 全偶数子序列：所有元素都是偶数，任意两个相邻元素的和为偶数
例如，对于数组 [2,4,6,8]，任意相邻元素的和都是偶数，因此整个数组是一个有效子序列。同样，[1,3,5,7] 也是一个有效子序列。
情况 2：相邻元素和全为奇数（模为 1）
这种情况下，每对相邻元素必须一个是奇数，一个是偶数。这意味着子序列必须是奇偶交替出现的：
- 奇、偶、奇、偶...
- 偶、奇、偶、奇...
例如，数组 [1,2,3,4] 是一个有效子序列，因为 1+2=3（奇），2+3=5（奇），3+4=7（奇）。同样，[2,3,4,5] 也是有效子序列。
通过以上分析，我们可以得出一个重要结论：最长的有效子序列必然是以下三种情况之一：
- 全奇数子序列（所有元素都是奇数）
- 全偶数子序列（所有元素都是偶数）
- 严格奇偶交替的子序列（奇 - 偶 - 奇 - 偶... 或 偶 - 奇 - 偶 - 奇...）
这是因为任何有效子序列都必须满足相邻元素和的奇偶性一致，而上述三种情况正好涵盖了所有可能的一致性模式。
算法设计思路
基于上述分析，我们可以设计出求解最长有效子序列的算法。算法的核心思想是分别计算上述三种情况的最大可能长度，然后取其中的最大值。
步骤 1：统计奇数和偶数的数量
全奇数子序列的最大可能长度就是数组中所有奇数的个数，全偶数子序列的最大可能长度就是数组中所有偶数的个数。因此，我们首先需要遍历数组，统计奇数和偶数的数量。
这个步骤非常直观，时间复杂度为 O (n)，其中 n 是数组的长度。空间复杂度为 O (1)，只需要两个计数器变量。
步骤 2：计算最长奇偶交替子序列的长度
接下来，我们需要计算最长的奇偶交替子序列的长度。这种子序列有两种可能的模式：
- 以奇数开头，然后奇偶交替（奇 - 偶 - 奇 - 偶...）
- 以偶数开头，然后奇偶交替（偶 - 奇 - 偶 - 奇...）
我们可以通过一次遍历数组来计算这两种模式的最大长度：
- 初始化两个变量：max_odd_start（以奇数开头的最长交替子序列长度）和 max_even_start（以偶数开头的最长交替子序列长度）
- 遍历数组中的每个元素：
- 如果当前元素是奇数，则更新 max_odd_start 为 max(max_odd_start, max_even_start + 1)
- 如果当前元素是偶数，则更新 max_even_start 为 max(max_even_start, max_odd_start + 1)
- 遍历结束后，最长奇偶交替子序列的长度就是 max(max_odd_start, max_even_start)
这种方法的原理是：当遇到一个奇数时，它可以接在以偶数结尾的交替子序列后面，形成一个更长的交替子序列；同理，当遇到一个偶数时，它可以接在以奇数结尾的交替子序列后面。
步骤 3：确定最终结果
最后，最长有效子序列的长度就是以下三个值中的最大值：
- 奇数的总个数
- 偶数的总个数
- 最长奇偶交替子序列的长度
代码实现（Python）
下面是基于上述思路的 Python 实现：
def longestValidSubsequence(nums):
# 处理空数组的情况
if not nums:
return 0
# 统计奇数和偶数的数量，同时计算最长奇偶交替子序列
count_odd = 0 # 奇数的总个数
count_even = 0 # 偶数的总个数
max_odd_start = 0 # 以奇数开头的最长交替子序列长度
max_even_start = 0 # 以偶数开头的最长交替子序列长度
for num in nums:
# 统计奇数和偶数
if num % 2 == 1:
count_odd += 1
# 更新以奇数开头的最长交替子序列长度
new_max_odd = max(max_odd_start, max_even_start + 1)
# 以偶数开头的不变
new_max_even = max_even_start
else:
count_even += 1
# 更新以偶数开头的最长交替子序列长度
new_max_even = max(max_even_start, max_odd_start + 1)
# 以奇数开头的不变
new_max_odd = max_odd_start
# 更新最大值
max_odd_start, max_even_start = new_max_odd, new_max_even
# 最长奇偶交替子序列的长度
max_alternating = max(max_odd_start, max_even_start)
# 返回三种情况中的最大值
return max(count_odd, count_even, max_alternating)代码实现（Java）
下面是对应的 Java 实现：
public class LongestValidSubsequence {
public static int longestValidSubsequence(int[] nums) {
// 处理空数组的情况
if (nums == null || nums.length == 0) {
return 0;
}
// 统计奇数和偶数的数量，同时计算最长奇偶交替子序列
int countOdd = 0; // 奇数的总个数
int countEven = 0; // 偶数的总个数
int maxOddStart = 0; // 以奇数开头的最长交替子序列长度
int maxEvenStart = 0; // 以偶数开头的最长交替子序列长度
for (int num : nums) {
// 统计奇数和偶数
if (num % 2 == 1) {
countOdd++;
// 更新以奇数开头的最长交替子序列长度
int newMaxOdd = Math.max(maxOddStart, maxEvenStart + 1);
// 以偶数开头的不变
int newMaxEven = maxEvenStart;
maxOddStart = newMaxOdd;
maxEvenStart = newMaxEven;
} else {
countEven++;
// 更新以偶数开头的最长交替子序列长度
int newMaxEven = Math.max(maxEvenStart, maxOddStart + 1);
// 以奇数开头的不变
int newMaxOdd = maxOddStart;
maxOddStart = newMaxOdd;
maxEvenStart = newMaxEven;
}
}
// 最长奇偶交替子序列的长度
int maxAlternating = Math.max(maxOddStart, maxEvenStart);
// 返回三种情况中的最大值
return Math.max(Math.max(countOdd, countEven), maxAlternating);
}
public static void main(String[] args) {
// 测试案例
int[] test1 = {1, 2, 3, 4, 5, 7, 8};
System.out.println(longestValidSubsequence(test1)); // 输出5
int[] test2 = {2, 4, 6, 8};
System.out.println(longestValidSubsequence(test2)); // 输出4
int[] test3 = {1, 3, 5, 7};
System.out.println(longestValidSubsequence(test3)); // 输出4
int[] test4 = {1, 2, 3, 4, 5, 6, 7};
System.out.println(longestValidSubsequence(test4)); // 输出7
int[] test5 = {};
System.out.println(longestValidSubsequence(test5)); // 输出0
}
}算法的扩展与思考
虽然这个问题本身并不复杂，但解决问题的思路可以应用到其他类似的子序列问题中。例如：
- 如果问题要求相邻元素的和能被 3 整除，我们可以采用类似的思路，分析元素模 3 的可能结果，然后设计相应的统计和计算方法。
- 对于更一般的相邻元素关系约束，我们可以尝试找出约束条件下的所有可能模式，然后分别计算每种模式下的最长子序列长度。
- 当约束条件比较复杂时，我们可能需要使用动态规划的方法，定义状态 dp [i][j] 表示以第 i 个元素结尾，且满足某种状态 j 的最长子序列长度。
总结
在这篇文章中，我们详细分析了如何寻找数组中最长的有效子序列，其中有效子序列的定义是任意相邻两个元素的和对 2 取模的结果都相同。
我们通过分析有效子序列的数学特征，发现最长有效子序列必然是以下三种情况之一：全奇数子序列、全偶数子序列或严格奇偶交替的子序列。基于这个发现，我们设计了一个高效的算法，通过统计奇数和偶数的数量，以及计算最长奇偶交替子序列的长度，最终得到问题的解。
算法的时间复杂度为 O (n)，空间复杂度为 O (1)，是一个非常高效的解决方案。这种通过分析问题本质特征来简化求解过程的思路，在解决其他算法问题时也非常有价值。
希望这篇文章能帮助你更好地理解子序列问题的求解思路，提升你在算法面试中的表现！