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 mainimport ( "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 ansif __name__ == "__main__": nums = [1, 2, 3, 4] result = maximum_length(nums) print(result)

在这里插入图片描述

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP