Medium

题目描述

给定一个整数数组 nums。

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

(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

解题思路

这道题的关键在于理解有效子序列的定义：相邻元素之和的奇偶性必须保持一致。

通过分析可以发现，有效的子序列只有以下几种模式：

  1. 全奇数序列：所有元素都是奇数
  2. 全偶数序列：所有元素都是偶数
  3. 奇偶交替序列：奇数-偶数-奇数-…
  4. 偶奇交替序列：偶数-奇数-偶数-…

解题思路：

  1. 统计所有奇数和偶数的个数，得到模式1和模式2的长度
  2. 对于交替模式，我们可以贪心地选择：遍历数组，根据当前需要的奇偶性选择第一个符合条件的元素
  3. 分别计算以奇数开始和以偶数开始的交替序列长度
  4. 返回四种模式中的最大值

这种方法的时间复杂度是O(n)，空间复杂度是O(1)，非常高效。

代码实现

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        int oddCount = 0, evenCount = 0;
        
        // 统计奇数和偶数个数
        for (int num : nums) {
            if (num % 2 == 0) evenCount++;
            else oddCount++;
        }
        
        // 计算奇偶交替序列长度（奇数开始）
        int oddEvenLen = 0;
        bool needOdd = true;
        for (int num : nums) {
            if ((num % 2 == 1) == needOdd) {
                oddEvenLen++;
                needOdd = !needOdd;
            }
        }
        
        // 计算偶奇交替序列长度（偶数开始）
        int evenOddLen = 0;
        bool needEven = true;
        for (int num : nums) {
            if ((num % 2 == 0) == needEven) {
                evenOddLen++;
                needEven = !needEven;
            }
        }
        
        return max({oddCount, evenCount, oddEvenLen, evenOddLen});
    }
};

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        odd_count = sum(1 for num in nums if num % 2 == 1)
        even_count = len(nums) - odd_count
        
        # 计算奇偶交替序列长度（奇数开始）
        odd_even_len = 0
        need_odd = True
        for num in nums:
            if (num % 2 == 1) == need_odd:
                odd_even_len += 1
                need_odd = not need_odd
        
        # 计算偶奇交替序列长度（偶数开始）
        even_odd_len = 0
        need_even = True
        for num in nums:
            if (num % 2 == 0) == need_even:
                even_odd_len += 1
                need_even = not need_even
        
        return max(odd_count, even_count, odd_even_len, even_odd_len)

public class Solution {
    public int MaximumLength(int[] nums) {
        int oddCount = 0, evenCount = 0;
        
        foreach (int num in nums) {
            if (num % 2 == 0) evenCount++;
            else oddCount++;
        }
        
        // 计算奇偶交替序列长度（奇数开始）
        int oddEvenLen = 0;
        bool needOdd = true;
        foreach (int num in nums) {
            if ((num % 2 == 1) == needOdd) {
                oddEvenLen++;
                needOdd = !needOdd;
            }
        }
        
        // 计算偶奇交替序列长度（偶数开始）
        int evenOddLen = 0;
        bool needEven = true;
        foreach (int num in nums) {
            if ((num % 2 == 0) == needEven) {
                evenOddLen++;
                needEven = !needEven;
            }
        }
        
        return Math.Max(Math.Max(oddCount, evenCount), Math.Max(oddEvenLen, evenOddLen));
    }
}

var maximumLength = function(nums) {
    let evenCount = 0;
    let oddCount = 0;
    let evenOddCount = 1;
    let oddEvenCount = 1;
    
    let lastEvenOdd = -1;
    let lastOddEven = -1;
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] % 2 === 0) {
            evenCount++;
            if (lastOddEven === 1) {
                oddEvenCount++;
            }
            lastEvenOdd = 0;
        } else {
            oddCount++;
            if (lastEvenOdd === 0) {
                evenOddCount++;
            }
            lastOddEven = 1;
        }
    }
    
    return Math.max(evenCount, oddCount, evenOddCount, oddEvenCount);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

相关题目