LeetCode 3201.找出有效子序列的最大长度 I：分类统计+贪心（一次遍历）

【LetMeFly】3201.找出有效子序列的最大长度 I：分类统计+贪心（一次遍历）

力扣题目链接：https://leetcode.cn/problems/find-the-maximum-length-of-valid-subsequence-i/

给你一个整数数组 nums。

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

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

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

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

 

示例 1：

输出： 4

解释：

最长的有效子序列是 [1, 2, 3, 4]。

示例 2：

输出： 6

解释：

最长的有效子序列是 [1, 2, 1, 2, 1, 2]。

示例 3：

输出： 2

解释：

最长的有效子序列是 [1, 3]。

 

提示：

• 2 <= nums.length <= 2 * 105
• 1 <= nums[i] <= 107

解题方法：分类统计

子序列如果是有效子序列(相邻两个元素之和 的奇偶性相同)，只有以下三种可能：

1. 全奇
2. 全偶
3. 一奇一偶交替排列

怎么一次遍历分别统计出这三种情况最长有效子序列呢？

• 使用一个变量$odd$，统计数组钟奇数元素的个数（那么偶数元素的个数就是$len(nums)-odd$）；
• 使用一个变量$last$，代表上一个选中元素是奇是偶；并使用一个元素$cnt$统计选中了多少个奇偶交替排列的元素。

所谓贪心，体现在当方案为奇偶交替时，遇到和上一个元素奇偶不同的元素一定选（不选白不选），遍历结束则能得到奇偶交替方案的最长长度。

举个例子：$2,0,3,5,4$这个数组，遍历时遇到2，选还是不选？

选，不选干嘛，以奇数开头吗？没必要，以奇数开头不就少选了个偶数吗。

而一次遍历过程中顺便统计下奇数个数就很简单了。

• 时间复杂度$O(x)$
• 空间复杂度$O(1)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-07-16 13:16:29* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-07-16 13:19:44*/
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endifclass Solution {
public:int maximumLength(vector<int>& nums) {int ans = 0;int odd = 0;bool last = nums[0] % 2 ? false : true;for (int t : nums) {if (t % 2) {odd++;if (!last) {last = true;ans++;}} else {if (last) {last = false;ans++;}}}return max(ans, max(odd, int(nums.size()) - odd));}
};

Python

'''
Author: LetMeFly
Date: 2025-07-16 13:16:29
LastEditors: LetMeFly.xyz
LastEditTime: 2025-07-16 13:36:53
'''
from typing import Listclass Solution:def maximumLength(self, nums: List[int]) -> int:ans = odd = 0last = False if nums[0] % 2 else Truefor t in nums:if t % 2:odd += 1if not last:last = Trueans += 1else:if last:last = Falseans += 1return max(ans, odd, len(nums) - odd)

Java

/** @Author: LetMeFly* @Date: 2025-07-16 13:16:29* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-07-16 13:41:23*/
class Solution {public int maximumLength(int[] nums) {int ans = 0;int odd = 0;boolean last = nums[0] % 2 == 0;for (int t : nums) {if (t % 2 == 0) {if (last) {last = false;ans++;}} else {odd++;if (!last) {last = true;ans++;}}}return Math.max(ans, Math.max(odd, nums.length - odd));}
}

Go

/** @Author: LetMeFly* @Date: 2025-07-16 13:16:29* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-07-16 13:40:18*/
package mainfunc maximumLength(nums []int) (ans int) {odd := 0last := nums[0] % 2 == 0for _, t := range nums {if t % 2 == 0 {if last {last = falseans++}} else {odd++if !last {last = trueans++}}}return max(ans, max(odd, len(nums) - odd))
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源