# LC 3201. Find the Maximum Length of Valid Subsequence I

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

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

You are given an integer array <code>nums</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]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2.</code>

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

A **subsequence** is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

**Example 1:**

<div class="example-block">
Input: <span class="example-io">nums = [1,2,3,4]

Output: <span class="example-io">4

Explanation:

The longest valid subsequence is <code>[1, 2, 3, 4]</code>.

**Example 2:**

<div class="example-block">
Input: <span class="example-io">nums = [1,2,1,1,2,1,2]

Output: 6

Explanation:

The longest valid subsequence is <code>[1, 2, 1, 2, 1, 2]</code>.

**Example 3:**

<div class="example-block">
Input: <span class="example-io">nums = [1,3]

Output: <span class="example-io">2

Explanation:

The longest valid subsequence is <code>[1, 3]</code>.

**Constraints:**

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

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

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

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(k^2 + nk) | O(k^2) |

## Note
套用[LC 3202. Find the Maximum Length of Valid Subsequence II](https://hackmd.io/@Alone0506/rJMvMJ1PR)的作法