日期: 2025 年 7 月 16 日

目标

给你一个整数数组 nums。

nums 的子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列：

• (sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2

返回 nums 的 最长的有效子序列 的长度。

一个 子序列 指的是从原数组中删除一些元素（也可以不删除任何元素），剩余元素保持原来顺序组成的新数组。

示例 1：

输入： nums = [1,2,3,4]
输出： 4
解释：
最长的有效子序列是 [1, 2, 3, 4]。

示例 2：

输入： nums = [1,2,1,1,2,1,2]
输出： 6
解释：
最长的有效子序列是 [1, 2, 1, 2, 1, 2]。

示例 3：

输入： nums = [1,3]
输出： 2
解释：
最长的有效子序列是 [1, 3]。

说明：

• 2 <= nums.length <= 2 * 10^5
• 1 <= nums[i] <= 10^7

思路

找出有效子序列的最大长度，使得子序列中相邻元素和的奇偶性相同。

注意到有效子序列中奇数下标的奇偶性必须相同，同时偶数下标的奇偶性也必须相同。总共四种情况：奇偶、奇奇、偶奇、偶偶。

代码

/**
 * @date 2025-07-16 8:43
 */
public class MaximumLength3201 {

    public int maximumLength(int[] nums) {
        int res = 0;
        for (int a = 0; a <= 1; a++) {
            for (int b = 0; b <= 1; b++) {
                int l = 0;
                int[] p = new int[]{a, b};
                int k = 0;
                for (int num : nums) {
                    if (num % 2 == p[k]) {
                        l++;
                        k ^= 1;
                    }
                }
                res = Math.max(l, res);
            }
        }
        return res;
    }

}

性能