2025-02-09：找出有效子序列的最大长度Ⅱ。用go语言，给定一个整数数组 nums 和一个正整数 k，我们定义一个子序列

福大大架构师每日一题

发布于 2025-02-10 15:23:52

6700

代码可运行

文章被收录于专栏：福大大架构师每日一题

运行总次数：0

代码可运行

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[1]

题目来自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 {
    letmut ans = 0;

    formin0..k {
        letmut f = vec![0; k asusize];
        for &x in &nums {
            letmod_x = x % k;
            f[mod_x asusize] = f[((m - mod_x + k) % k) asusize] + 1;
            ans = ans.max(f[mod_x asusize]);
        }
    }

    ans
}

fnmain() {
    letnums = vec![1, 2, 3, 4, 5];
    letk = 2;
    letresult = maximum_length(nums, k);
    println!("{}", result);
}

在这里插入图片描述

Python完整代码如下：

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

defmaximum_length(nums, k):
    ans = 0
    
    for m inrange(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)