目标
给你一个整数数组 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
思路
找出数组 nums 的有效子序列的最大长度，有效子序列指相邻元素之和模 k 的值相等。
3201.找出有效子序列的最大长度I 是本题 k = 2 的特例。这个题目可能的组合有 k^2 种。
定义 dp[i][j] 表示子序列后两项模 k 的值为 i 和 j 的子序列长度。
代码
/**
* @date 2025-07-16 10:18
*/
public class MaximumLength3202 {
public int maximumLength(int[] nums, int k) {
int[][] dp = new int[k][k];
int res = 0;
for (int num : nums) {
int m = num % k;
for (int i = 0; i < k; i++) {
dp[i][m] = dp[m][i] + 1;
res = Math.max(res, dp[i][m]);
}
}
return res;
}
}
性能
