跟昨天那題很像
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
}