diff options
Diffstat (limited to 'find_max_len_valid_subseq2.py')
-rw-r--r-- | find_max_len_valid_subseq2.py | 57 |
1 files changed, 57 insertions, 0 deletions
diff --git a/find_max_len_valid_subseq2.py b/find_max_len_valid_subseq2.py new file mode 100644 index 0000000..6a1bfa4 --- /dev/null +++ b/find_max_len_valid_subseq2.py @@ -0,0 +1,57 @@ +# 3202. Find the Maximum Length of Valid Subsequence II + +""" +you are given an integer array 'nums' and a positive integer 'k'. a +subsequence 'sub' of 'nums' with length 'x' is called valid if it satisfies +'(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x +- 1]) % k'. return the length of the longest valid subsequence of 'nums' +""" + + +class Solution(object): + def maximumLength(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + left = [[] for _ in range(k)] + right = [i % k for i in nums] + for i, j in enumerate(right): + left[j].append(i) + m = max(len(i) for i in left) if k > 0 else 0 + if k == 0 or k == 1: + return m + for x in range(k): + for y in range(x + 1, k): + a, b = left[x], left[y] + la, lb = len(a), len(b) + if la == 0 and lb == 0: + continue + i, j = 0, 0 + sx, sy = 0, 0 + while i < la or j < lb: + if j == lb or (i < la and a[i] < b[j]): + nx = 1 + if sy > 0: + nx = sy + 1 + if nx > sx: + sx = nx + i += 1 + else: + ny = 1 + if sx > 0: + ny = sx + 1 + if ny > sy: + sy = ny + j += 1 + curr = max(sx, sy) + if curr > m: + m = curr + return m + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumLength(nums=[1, 2, 3, 4, 5], k=2)) + print(obj.maximumLength(nums=[1, 4, 2, 3, 1, 4], k=3)) |