# LC 3202. Find the Maximum Length of Valid Subsequence II

### [Problem link](https://leetcode.com/problems/find-the-maximum-length-of-valid-subsequence-ii/)

###### tags: `leedcode` `medium` `c++` `DP`

You are given an integer array <code>nums</code> and a **positive** integer <code>k</code>.
A <span data-keyword="subsequence-array">subsequence <code>sub</code> of <code>nums</code> with length <code>x</code> is called **valid** if it satisfies:

- <code>(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k.</code>

Return the length of the **longest** **valid** subsequence of <code>nums</code>.

**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 <code>[1, 2, 3, 4, 5]</code>.

**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 <code>[1, 4, 1, 4]</code>.

**Constraints:**

- <code>2 <= nums.length <= 10³</code>
- <code>1 <= nums[i] <= 10⁷</code>
- <code>1 <= k <= 10³</code>

## Solution 1 - DP
#### C++

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        vector<vector<int>> dp(k, vector<int>(k, 0));
        int ans = 0;
        for (int num: nums) {
            num %= k;
            for (int i = 0; i < k; i++) {
                dp[i][num] = dp[num][i] + 1;
                ans = max(ans, dp[i][num]);
            }
        }
        return ans;
    }
};

>### Complexity
>n = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(k^2 + nk) | O(k^2) |

## Note
sol1:
dp[i][j]: 以i, j為結尾的subsequence最大長度