4110. 找出有效子序列的最大长度 III 🔒

难度中等

题目描述

给你一个整数数组 nums 和一个正整数 k。

如果 nums 的一个子序列中，任意一对相邻元素之和都能被 k 整除，则称该子序列是有效的。

长度为 1 的子序列始终有效。

返回 nums 的最长有效子序列的长度。

示例 1：

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

输出： 4

解释：

选取子序列 [1, 2, 4, 5]。
相邻元素之和为 1 + 2 = 3、2 + 4 = 6 和 4 + 5 = 9，都能被 3 整除。
不存在长度大于 4 的有效子序列。

示例 2：

输入： nums = [5,10,15], k = 5

输出： 3

解释：

选取整个数组 [5, 10, 15]。
相邻元素之和为 5 + 10 = 15 和 10 + 15 = 25，都能被 5 整除。
每个元素都是 5 的倍数，因此任意两个元素都可以在有效子序列中相邻，答案为 3。

示例 3：

输入： nums = [1,3,5,7,9], k = 4

输出： 5

解释：

选取整个数组 [1, 3, 5, 7, 9]。
相邻元素之和为 1 + 3 = 4、3 + 5 = 8、5 + 7 = 12 和 7 + 9 = 16，都能被 4 整除。
余数在 1 和 3 之间交替，二者之和为 4，因此答案为 5。

提示：

2 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁵

解法

方法一：动态规划

思考

对每个位置向前枚举所有可以与它相邻的元素，比较次数是 \(O(n^2)\)。这里 \(n\) 达到 \(10^5\)，这一枚举无法通过。

相邻两数之和能被 \(k\) 整除，当且仅当它们对 \(k\) 的余数 \(x\) 与 \(y\) 满足 \(y=(k-x)\bmod k\)。前驱余数由当前余数唯一确定，有效子序列的余数只能在 \(x\) 与 \(y\) 之间交替。当 \(x=y\) 时，子序列里每个元素的余数都相同。

同一余数的各个位置里，只需留下最靠右的一个。更靠后的元素只能接到互补余数当前最右的下标上，这条链的长度不会短于任何更早的同余数位置。

因此我们从左到右扫描数组，用哈希表 \(\textit{last}\) 记录每个余数最后出现的下标，并用 \(f[i]\) 记录以位置 \(i\) 结尾的最长有效子序列长度。遇到余数 \(x\) 时，若 \(y\) 已经出现，就用 \(f[\textit{last}[y]]+1\) 更新 \(f[i]\)，再把 \(\textit{last}[x]\) 改写为 \(i\)。

我们用 \(f[i]\) 表示以 \(\textit{nums}[i]\) 结尾的最长有效子序列的长度，初始时每个 \(f[i]=1\)。哈希表 \(\textit{last}\) 记录每个余数最后一次出现的下标。

从左到右扫描数组。对于位置 \(i\)，令 \(x=\textit{nums}[i]\bmod k\)， \(y=(k-x)\bmod k\)。若 \(\textit{last}\) 中已有余数 \(y\)，记其下标为 \(j\)，则将 \(f[i]\) 更新为 \(\max(f[i], f[j]+1)\)。随后令 \(\textit{last}[x]=i\)。

答案为所有 \(f[i]\) 的最大值。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(\textit{nums}\) 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def maximumLength(self, nums: list[int], k: int) -> int:
        f = [1] * len(nums)
        last = {}
        ans = 1
        for i, x in enumerate(nums):
            x %= k
            y = (k - x) % k
            if y in last:
                j = last[y]
                f[i] = max(f[i], f[j] + 1)
                ans = max(ans, f[i])
            last[x] = i
        return ans

class Solution {
    public int maximumLength(int[] nums, int k) {
        int n = nums.length;
        int[] f = new int[n];
        Arrays.fill(f, 1);
        Map<Integer, Integer> last = new HashMap<>();
        int ans = 1;
        for (int i = 0; i < n; i++) {
            int x = nums[i] % k;
            int y = (k - x) % k;
            if (last.containsKey(y)) {
                int j = last.get(y);
                f[i] = Math.max(f[i], f[j] + 1);
                ans = Math.max(ans, f[i]);
            }
            last.put(x, i);
        }
        return ans;
    }
}

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> f(n, 1);
        unordered_map<int, int> last;
        int ans = 1;
        for (int i = 0; i < n; i++) {
            int x = nums[i] % k;
            int y = (k - x) % k;
            if (last.count(y)) {
                int j = last[y];
                f[i] = max(f[i], f[j] + 1);
                ans = max(ans, f[i]);
            }
            last[x] = i;
        }
        return ans;
    }
};

func maximumLength(nums []int, k int) int {
    n := len(nums)
    f := make([]int, n)
    for i := range f {
        f[i] = 1
    }
    last := map[int]int{}
    ans := 1
    for i, v := range nums {
        x := v % k
        y := (k - x) % k
        if j, ok := last[y]; ok {
            f[i] = max(f[i], f[j]+1)
            ans = max(ans, f[i])
        }
        last[x] = i
    }
    return ans
}

function maximumLength(nums: number[], k: number): number {
    const n = nums.length;
    const f: number[] = new Array(n).fill(1);
    const last = new Map<number, number>();
    let ans = 1;
    for (let i = 0; i < n; i++) {
        const x = nums[i] % k;
        const y = (k - x) % k;
        if (last.has(y)) {
            const j = last.get(y)!;
            f[i] = Math.max(f[i], f[j] + 1);
            ans = Math.max(ans, f[i]);
        }
        last.set(x, i);
    }
    return ans;
}

4110. 找出有效子序列的最大长度 III 🔒

题目描述

解法

方法一：动态规划

评论