跟昨天那题很像
3202. Find the Maximum Length of Valid Subsequence II
看了一下题目限制, nums长度跟k都不超过10^3
这样就把(sub[0] + sub[1]) %k后的每一种余数 0 ~ k-1进行个别计算
假设现在要找的余数是a
且nums[i] % k == b
那nums[i]要跟nums[j]相加才能使 ( nums[i] + nums[j] ) % k = a
nums[j]满足 nums[j] % k = (a + k - b) % k
就用一个矩阵纪录余数是0 ~ k-1目前subsequence的长度
找出最大值就好
golang code :
func maximumLength(nums []int, k int) int {
n, ans := len(nums), 0
for i := 0; i < k; i++ {
dp := make([]int, k)
for j := 0; j < n; j++ {
cur := nums[j] % k
need := ((i + k) - cur) % k
dp[cur] = dp[need] + 1
ans = max(dp[cur], ans)
}
}
return ans
}