3202. 找出有效子序列的最大长度 II(1974)

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

nums 的一个

子序列

sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列 ：

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

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

示例 1：

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

**输出：**5

解释：

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

示例 2：

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

**输出：**4

解释：

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

提示：

  • 2 <= nums.length <= 10^3
  • 1 <= nums[i] <= 10^7
  • 1 <= k <= 10^3

值域dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maximumLength(int[] nums, int k) {
        int n = nums.length, res = 0;
        for (int i = 0; i < n; i++) nums[i] %= k;
        // f[i][j]: 以nums[i]结尾,等式值为j的最长子序列的长度
        int f[][] = new int[n][k];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {  // 遍历上一项nums[j]
                // 则当前等式的值 就是 (nums[i]+nums[j])%k
                int value = (nums[i]+nums[j])%k;
                f[i][value] = f[j][value] + 1;
                res = Math.max(res, f[i][value]);
            }
        }
        return res+1;
    }
}

条件转换 + dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maximumLength(int[] nums, int k) {
        int n = nums.length, res = 0;
        for (int i = 0; i < n; i++) nums[i] %= k;
        // 题目等价于：寻找一个最长的子序列，满足子序列奇数项都相同，偶数项都相同。
        // f[i][j]: 子序列最后两项 mod k 分别等于 i 和 j
        int f[][] = new int[k][k];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                f[j][nums[i]] = f[nums[i]][j] + 1;
                res = Math.max(res, f[j][nums[i]]);
            }
        }
        return res;
    }
}

本题数据较弱，也可以暴力一点，先记录下所有mod k的余数对应的所有索引下标，然后暴力双重遍历这个索引下标，寻找到最长的奇数项都相同，偶数项都相同的子序列长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int maximumLength(int[] nums, int k) {
        int n = nums.length, res = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {  // 记录所有mod k的余数对应的所有索引下标
            nums[i] %= k;
            map.computeIfAbsent(nums[i], key -> new ArrayList<>());
            map.get(nums[i]).add(i);
        }
        for (int k1 : map.keySet()) {  // 遍历奇数项所有余数情况
            List<Integer> v1 = map.get(k1);
            for (int k2 : map.keySet()) {  // 遍历偶数项所有余数情况
                List<Integer> v2 = map.get(k2);
                int idx = -1, cur = 0, c = 0;
                for (int i = 0, j = 0; i < v1.size() || j < v2.size();) {  // 奇数项和偶数项交替组成子序列
                    if (c % 2 == 0 && i < v1.size()) {
                        if (idx < v1.get(i)) {
                            idx = v1.get(i);
                            cur++;
                            c++;
                        }
                        i++;
                    }
                    else if (c % 2 == 1 && j < v2.size()) {
                        if (idx < v2.get(j)) {
                            idx = v2.get(j);
                            cur++;
                            c++;
                        }
                        j++;
                    }
                    else break;
                }
                res = Math.max(res, cur);
            }
        }
        return res;
    }
}