- Leetcode 3202. Find the Maximum Length of Valid Subsequence II
- 1. 解題思路
- 2. 代碼實現
- 題目鏈接：3202. Find the Maximum Length of Valid Subsequence II
1. 解題思路
這一題的話是上一題3201. Find the Maximum Length of Valid Subsequence I的升級版，主要就是將除數2調整為任意正數k，但是本質上還是一樣的，我們同樣有奇數位和偶數位上的數必然對k有著相同的余數，此時，我們只需要考察前兩個元素的余數組合，然后考察他們的所有位置能夠組成的交叉序列的最大長度即可。
當前兩個元素的余數相同時，我們能夠獲得的最大子序列的長度就是k的余數相同的元素出現的最大頻次。
當前兩個元素的余數不同時，我們能夠快速得到兩個余數的位置序列，然后我們通過貪婪算法配合二分搜索即可快速得到他們能夠組成的最大交叉序列長度。
最后，如果兩個序列的長度之后都小于當前已經獲得的最大序列長度了，我們就可以直接跳過這些可能性了，由此，我們即可進一步對問題進行剪枝，從而得到我們最終的答案。
2. 代碼實現
給出python代碼實現如下：
class Solution:def maximumLength(self, nums: List[int], k: int) -> int:locs = defaultdict(list)for i, x in enumerate(nums):locs[x%k].append(i)ans = max(len(x) for x in locs.values())def get_max_length(s1, s2):n, m = len(s1), len(s2)i, j = 0, 0cnt = 1 if s2[0] < s1[0] else 0while i < n:cnt += 1j = bisect.bisect_left(s2, s1[i])if j < m:cnt += 1else:breaki = bisect.bisect_left(s1, s2[j])return cntfor i in range(k-1):if locs[i] == []:continuefor j in range(i+1, k):if len(locs[i]) + len(locs[j]) <= ans:continuecnt = get_max_length(locs[i], locs[j])ans = max(ans, cnt)return ans
提交代碼評測得到：耗時277ms，占用內存16.8MB。
