2025-02-08：找出有效子序列的最大长度Ⅰ。用go语言，给定一个整数数组 nums，我们需要找出其最长的“有效子序列”的长

福大大架构师每日一题

发布于 2025-02-10 15:24:14

3500

代码可运行

运行总次数：0

代码可运行

2025-02-08：找出有效子序列的最大长度Ⅰ。用go语言，给定一个整数数组 nums，我们需要找出其最长的“有效子序列”的长度。有效子序列的定义为：一个长度为 x 的子序列需要满足以下条件：对于子序列中的任意连续两个元素，前两个元素之和的奇偶性（即 (sub[i] + sub[i+1]) % 2）在整个子序列中保持一致。也就是说，所有相邻元素之和的奇偶性都应该相同。

简而言之，我们要找出从数组中提取的符合这些条件的最长的子序列，并返回这个子序列的长度。

2 <= nums.length <= 2 * 100000。

1 <= nums[i] <= 10000000。

输入： nums = [1,2,3,4]。

输出： 4。

解释：

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

答案2025-02-08：

chatgpt[1]

题目来自leetcode3201。

大体步骤如下：

1.创建一个函数 maximumLength(nums []int) int 用于计算最长有效子序列的长度。

2.初始化变量 ans 为 0，k 为 2，f 为一个长度为 k 的整型数组。

3.循环 m 从 0 到 k：

3.1.调用 clear(f) 函数，清空数组 f。

3.2.遍历数组 nums 中的每个元素 x：

3.2.1.对 x 取模 k 得到余数。

3.2.2.计算 f[x] 为 f[(m-x+k)%k] + 1。

3.2.3.更新 ans 为 f[x] 和当前 ans 的较大值。

4.返回 ans 作为最长有效子序列的长度。

5.在 main 函数中，给定数组 nums := []int{1, 2, 3, 4}，调用 maximumLength(nums) 函数并打印结果。

总的时间复杂度：

• 外层循环次数为 O(k)，内层遍历数组 nums 的时间复杂度为 O(n)，其中 n 是 nums 的长度。
• 因此总的时间复杂度为 O(k*n)。

总的额外空间复杂度：

• 需要一个长度为 k 的整型数组 f 存储中间结果，因此额外空间复杂度为 O(k)。

Go完整代码如下：

package main

import (
    "fmt"
)

func maximumLength(nums []int) int {
    ans := 0
    k := 2
    f := make([]int, k)
    for m := 0; m < k; m++ {
        clear(f)
        for _, x := range nums {
            x %= k
            f[x] = f[(m-x+k)%k] + 1
            ans = max(ans, f[x])
        }
    }
    return ans
}

func main() {
    nums := []int{1, 2, 3, 4}
    result := maximumLength(nums)
    fmt.Println(result)
}

Rust完整代码如下：

fn maximum_length(nums: Vec<i32>) -> i32 {
    let mut ans = 0;
    let k = 2 as i32;
    let mut f = vec![0; k as usize];

    for m in 0..k {
        f.iter_mut().for_each(|x| *x = 0); // 清空 f 数组

        for &x in &nums {
            let x_mod = (x % k + k) % k; // 计算 x % k 的结果，确保结果为非负数
            f[x_mod as usize] = f[((m - x_mod + k) % k) as usize] + 1; // 更新 f 数组
            ans = ans.max(f[x_mod as usize]); // 更新答案
        }
    }
    ans
}

fn main() {
    let nums = vec![1, 2, 3, 4];
    let result = maximum_length(nums);
    println!("{}", result);
}

Python完整代码如下：

# -*-coding:utf-8-*-

def maximum_length(nums):
    ans = 0
    k = 2
    f = [0] * k

    for m in range(k):
        f = [0] * k  # 清空 f 数组

        for x in nums:
            x_mod = x % k
            f[x_mod] = f[(m - x_mod + k) % k] + 1  # 更新 f 数组
            ans = max(ans, f[x_mod])  # 更新答案

    return ans

if __name__ == "__main__":
    nums = [1, 2, 3, 4]
    result = maximum_length(nums)
    print(result)