aboutsummaryrefslogtreecommitdiff
path: root/find_max_len_valid_subseq2.py
diff options
context:
space:
mode:
Diffstat (limited to 'find_max_len_valid_subseq2.py')
-rw-r--r--find_max_len_valid_subseq2.py57
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))