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：

输入： 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 * 105
• 1 <= nums[i] <= 107

解题方法：分类统计

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

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

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

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

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

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

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

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

• 时间复杂度$O(n)$，其中$n=len(nums)$
• 空间复杂度$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"
#endif

class 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 List

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        ans = odd = 0
        last = False if nums[0] % 2 else True
        for t in nums:
            if t % 2:
                odd += 1
                if not last:
                    last = True
                    ans += 1
            else:
                if last:
                    last = False
                    ans += 1
        return 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 main

func maximumLength(nums []int) (ans int) {
    odd := 0
    last := nums[0] % 2 == 0
    for _, t := range nums {
        if t % 2 == 0 {
            if last {
                last = false
                ans++
            }
        } else {
            odd++
            if !last {
                last = true
                ans++
            }
        }
    }
    return max(ans, max(odd, len(nums) - odd))
}

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

千篇源码题解已开源