2025-02-09：找出有效子序列的最大长度Ⅱ。用go语言，给定一个整数数组 nums 和一个正整数 k，我们定义一个子序列 sub 的长度为 x，如果满足以下条件，则称为有效子序列：

(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == … == (sub[x - 2] + sub[x - 1]) % k

我们的目标是返回数组 nums 中最长有效子序列的长度。

2 <= nums.length <= 1000。

1 <= nums[i] <= 10000000。

1 <= k <= 1000。

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

输出：5。

解释：

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

答案2025-02-09：

chatgpt

题目来自leetcode3202。

大体步骤如下：

1.声明一个长度为 k 的数组 f，用来记录当前余数 m 对应的子序列长度。初始时全部设为 0。

2.循环遍历 m 从 0 到 k-1：

2.1.在每次循环开始时要清空数组 f 的值，这里的 clear(f) 操作可能是将数组 f 的值全部置为 0。

2.2.再次遍历原始数组 nums 中的每个数字 x：

2.2.1.将当前数字取余 k，得到 x 对 k 取余的结果。

2.2.2.根据 (m - x + k) % k 计算出当前数字 x 对应的余数应该是多少。

2.2.3.更新 f[x] 的值为 f[(m - x + k) % k] + 1，即前一个余数为 (m - x + k) % k 对应的子序列长度加 1。

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

3.返回最终计算得到的最长有效子序列长度。

总的时间复杂度为 O(k*n)，其中 n 表示数组 nums 的长度。

总的额外空间复杂度为 O(k)。

Go完整代码如下：

package main

import (
	"fmt"
)

func maximumLength(nums []int, k int) (ans int) {
	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
}


func main() {
	nums := []int{1,2,3,4,5}![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/b145d7f2b1a04b778992d36fed265949.png)

	k := 2
	result := maximumLength(nums,k)
	fmt.Println(result)
}

Rust完整代码如下：

fn maximum_length(nums: Vec<i32>, k: i32) -> i32 {
    let mut ans = 0;

    for m in 0..k {
        let mut f = vec![0; k as usize];
        for &x in &nums {
            let mod_x = x % k;
            f[mod_x as usize] = f[((m - mod_x + k) % k) as usize] + 1;
            ans = ans.max(f[mod_x as usize]);
        }
    }

    ans
}

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

Python完整代码如下：

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

def maximum_length(nums, k):
    ans = 0
    
    for m in range(k):
        f = [0] * k  # 初始化长度为 k 的数组
        for x in nums:
            x %= k  # 计算 x 对 k 的模
            f[x] = f[(m - x + k) % k] + 1  # 更新 f
            ans = max(ans, f[x])  # 更新答案
    return ans

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