{leetcode}/problems/find-the-maximum-length-of-valid-subsequence-ii/[LeetCode - 3202. Find the Maximum Length of Valid Subsequence II ^]
You are given an integer array nums and a positive integer k.
A <span data-keyword="subsequence-array">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.
Example 1:
<div class="example-block"> Input: <span class="example-io">nums = [1,2,3,4,5], k = 2
Output: <span class="example-io">5
Explanation:
The longest valid subsequence is [1, 2, 3, 4, 5].
Example 2:
<div class="example-block"> Input: <span class="example-io">nums = [1,4,2,3,1,4], k = 3
Output: <span class="example-io">4
Explanation:
The longest valid subsequence is [1, 4, 1, 4].
Constraints:
-
2 ⇐ nums.length ⇐ 103 -
1 ⇐ nums[i] ⇐ 107 -
1 ⇐ k ⇐ 103