Welcome to Subscribe On Youtube
3202. Find the Maximum Length of Valid Subsequence II
Description
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.
Example 1:
Input: nums = [1,2,3,4,5], k = 2
Output: 5
Explanation:
The longest valid subsequence is [1, 2, 3, 4, 5].
Example 2:
Input: nums = [1,4,2,3,1,4], k = 3
Output: 4
Explanation:
The longest valid subsequence is [1, 4, 1, 4].
Constraints:
2 <= nums.length <= 1031 <= nums[i] <= 1071 <= k <= 103
Solutions
Solution 1: Dynamic Programming
Based on the problem description, we know that for a subsequence $a_1, a_2, a_3, \cdots, a_x$, if it satisfies $(a_1 + a_2) \bmod k = (a_2 + a_3) \bmod k$, then $a_1 \bmod k = a_3 \bmod k$. This means that the result of taking modulo $k$ for all odd-indexed elements is the same, and the result for all even-indexed elements is the same as well.
We can solve this problem using dynamic programming. Define the state $f[x][y]$ as the length of the longest valid subsequence where the last element modulo $k$ equals $x$, and the second to last element modulo $k$ equals $y$. Initially, $f[x][y] = 0$.
Iterate through the array $nums$, and for each number $x$, we get $x = x \bmod k$. Then, we can enumerate the sequences where two consecutive numbers modulo $j$ yield the same result, where $j \in [0, k)$. Thus, the previous number modulo $k$ would be $y = (j - x + k) \bmod k$. At this point, $f[x][y] = f[y][x] + 1$.
The answer is the maximum value among all $f[x][y]$.
The time complexity is $O(n \times k)$, and the space complexity is $O(k^2)$. Here, $n$ is the length of the array $\text{nums}$, and $k$ is the given positive integer.
-
class Solution { public int maximumLength(int[] nums, int k) { int[][] f = new int[k][k]; int ans = 0; for (int x : nums) { x %= k; for (int j = 0; j < k; ++j) { int y = (j - x + k) % k; f[x][y] = f[y][x] + 1; ans = Math.max(ans, f[x][y]); } } return ans; } } -
class Solution { public: int maximumLength(vector<int>& nums, int k) { int f[k][k]; memset(f, 0, sizeof(f)); int ans = 0; for (int x : nums) { x %= k; for (int j = 0; j < k; ++j) { int y = (j - x + k) % k; f[x][y] = f[y][x] + 1; ans = max(ans, f[x][y]); } } return ans; } }; -
class Solution: def maximumLength(self, nums: List[int], k: int) -> int: f = [[0] * k for _ in range(k)] ans = 0 for x in nums: x %= k for j in range(k): y = (j - x + k) % k f[x][y] = f[y][x] + 1 ans = max(ans, f[x][y]) return ans -
func maximumLength(nums []int, k int) (ans int) { f := make([][]int, k) for i := range f { f[i] = make([]int, k) } for _, x := range nums { x %= k for j := 0; j < k; j++ { y := (j - x + k) % k f[x][y] = f[y][x] + 1 ans = max(ans, f[x][y]) } } return } -
function maximumLength(nums: number[], k: number): number { const f: number[][] = Array.from({ length: k }, () => Array(k).fill(0)); let ans: number = 0; for (let x of nums) { x %= k; for (let j = 0; j < k; ++j) { const y = (j - x + k) % k; f[x][y] = f[y][x] + 1; ans = Math.max(ans, f[x][y]); } } return ans; }