# Find the Maximum Length of Valid Subsequence I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-maximum-length-of-valid-subsequence-i)
Canonical: https://scaleengineer.com/dsa/problems/find-the-maximum-length-of-valid-subsequence-i
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
You are given an integer array `nums`. 

A subsequence `sub` of `nums` with length `x` is called **valid** if it satisfies:

* `(sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2.`

Return the length of the **longest** **valid** subsequence of `nums`.

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:**

**Input:** nums = \[1,2,3,4\]

**Output:** 4

**Explanation:**

The longest valid subsequence is `[1, 2, 3, 4]`.

**Example 2:**

**Input:** nums = \[1,2,1,1,2,1,2\]

**Output:** 6

**Explanation:**

The longest valid subsequence is `[1, 2, 1, 2, 1, 2]`.

**Example 3:**

**Input:** nums = \[1,3\]

**Output:** 2

**Explanation:**

The longest valid subsequence is `[1, 3]`.

**Constraints:**

* `2 <= nums.length <= 2 * 105`
* `1 <= nums[i] <= 107`

# Approaches
## Brute-Force with Backtracking
This approach involves generating every possible subsequence of the input array `nums`. For each subsequence, we perform a check to see if it meets the criteria of a "valid" subsequence as defined in the problem. We keep track of the length of the longest valid subsequence encountered and return it as the final answer.
**Time:** O(N * 2^N). There are 2^N possible subsequences. For each subsequence, the validity check can take up to O(N) time. · **Space:** O(N), where N is the number of elements in `nums`. This space is used by the recursion stack and to store the current subsequence being built.
**Pros:** Guaranteed to find the correct solution.; It is a straightforward implementation of the problem definition.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error on any reasonably sized input.
### Explanation
The core of this method is a backtracking algorithm. We can define a recursive helper function that builds subsequences element by element. For each element in the original array, we decide whether to include it in our current subsequence or not. This branching creates a decision tree that covers all 2^N possible subsequences.

When the recursion reaches the end of the input array, we have a complete subsequence. We then pass this subsequence to a validation function. The validation function checks if the subsequence has a length of at least 2. If it does, it calculates the parity of the sum of the first two elements, `(sub[0] + sub[1]) % 2`. It then iterates through the rest of the adjacent pairs, ensuring they all yield the same sum parity. If the subsequence is valid, we update our global maximum length. While simple to conceptualize, the sheer number of subsequences makes this approach impractical for the given constraints.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    int maxLength = 0;

    public int maximumLength(int[] nums) {
        // Any subsequence of length 1 is valid. Since nums.length >= 2, we can find a pair.
        // The smallest non-trivial valid subsequence has length 2.
        // We can initialize maxLength to 0, and it will be updated.
        generateSubsequences(nums, 0, new ArrayList<>());
        return maxLength;
    }

    private void generateSubsequences(int[] nums, int index, List<Integer> currentSub) {
        if (index == nums.length) {
            if (isValid(currentSub)) {
                maxLength = Math.max(maxLength, currentSub.size());
            }
            return;
        }

        // Decision 1: Exclude nums[index]
        generateSubsequences(nums, index + 1, currentSub);

        // Decision 2: Include nums[index]
        currentSub.add(nums[index]);
        generateSubsequences(nums, index + 1, currentSub);
        currentSub.remove(currentSub.size() - 1); // Backtrack
    }

    private boolean isValid(List<Integer> sub) {
        if (sub.size() < 2) {
            return true; // Vacuously true, length will be 0 or 1.
        }
        int expectedParity = (sub.get(0) + sub.get(1)) % 2;
        for (int i = 1; i < sub.size() - 1; i++) {
            if ((sub.get(i) + sub.get(i + 1)) % 2 != expectedParity) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Create a recursive function, for example, `generate(index, currentSubsequence)`, to explore all possibilities.
- The function will have two recursive calls for each element `nums[index]`:
  1. One call that excludes `nums[index]` from the subsequence.
  2. Another call that includes `nums[index]` in the subsequence.
- The base case for the recursion is when `index` reaches the end of the array `nums`.
- In the base case, check if the `currentSubsequence` is valid. A subsequence `sub` is valid if the parity of the sum of adjacent elements, `(sub[i] + sub[i+1]) % 2`, is constant for all `i`.
- Maintain a global variable to keep track of the maximum length of a valid subsequence found so far.
- Since any subsequence of length less than 2 is trivially valid, and the constraints guarantee `nums.length >= 2`, the answer will be at least 2.

## Dynamic Programming
A more optimized approach than brute-force is to use dynamic programming. We can determine the length of the longest valid subsequence ending at each position `i` by looking at the results for all previous positions `j < i`. This avoids re-computation by storing and reusing intermediate results.
**Time:** O(N^2) because of the nested loops required to fill the DP tables. · **Space:** O(N) to store the two DP arrays, `dp_same` and `dp_alt`.
**Pros:** Significantly faster than the brute-force approach.; It's a standard DP pattern that is applicable to many subsequence problems.
**Cons:** The O(N^2) time complexity is too slow for the given constraints (`N <= 2 * 10^5`), leading to a 'Time Limit Exceeded' error.
### Explanation
This method is based on the classic Longest Increasing Subsequence (LIS) problem structure. We can categorize the valid subsequences into two types:
1.  Those where all elements have the same parity (e.g., all even or all odd).
2.  Those where elements have alternating parities (e.g., even, odd, even, ...).

We can use two DP arrays to track the lengths of these two types of subsequences. Let `dp_same[i]` be the length of the longest same-parity subsequence ending with `nums[i]`, and `dp_alt[i]` be the length of the longest alternating-parity subsequence ending with `nums[i]`. To calculate `dp_same[i]`, we find a `j < i` such that `nums[j]` has the same parity as `nums[i]` and `dp_same[j]` is maximized. Then, `dp_same[i] = 1 + dp_same[j]`. A similar logic applies to `dp_alt[i]`, but we look for `nums[j]` with a different parity. The overall answer is the maximum value found across both DP arrays.

```java
import java.util.Arrays;

class Solution {
    public int maximumLength(int[] nums) {
        int n = nums.length;
        if (n <= 2) {
            return n;
        }

        // dp_same[i]: length of longest subsequence with same parity ending at index i
        int[] dp_same = new int[n];
        // dp_alt[i]: length of longest subsequence with alternating parity ending at index i
        int[] dp_alt = new int[n];
        Arrays.fill(dp_same, 1);
        Arrays.fill(dp_alt, 1);

        int maxLen = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if ((nums[i] % 2) == (nums[j] % 2)) {
                    dp_same[i] = Math.max(dp_same[i], 1 + dp_same[j]);
                } else {
                    dp_alt[i] = Math.max(dp_alt[i], 1 + dp_alt[j]);
                }
            }
            maxLen = Math.max(maxLen, Math.max(dp_same[i], dp_alt[i]));
        }

        return maxLen;
    }
}
```
### Algorithm
- Initialize two DP arrays, `dp_same` and `dp_alt`, both of size `n` and filled with 1s. `dp_same[i]` will store the length of the longest same-parity subsequence ending at `nums[i]`, and `dp_alt[i]` for alternating-parity.
- Iterate with an outer loop for `i` from 0 to `n-1`.
- Inside, have an inner loop for `j` from 0 to `i-1`.
- In the inner loop, compare the parities of `nums[i]` and `nums[j]`.
  - If `(nums[i] % 2) == (nums[j] % 2)`, it means they can extend a same-parity subsequence. Update `dp_same[i] = max(dp_same[i], 1 + dp_same[j])`.
  - If their parities are different, they can extend an alternating-parity subsequence. Update `dp_alt[i] = max(dp_alt[i], 1 + dp_alt[j])`.
- After the inner loop, update a variable `maxLen` with the maximum value seen so far in `dp_same[i]` and `dp_alt[i]`.
- Return `maxLen` after the loops complete.

## Greedy Single-Pass Approach
The most efficient solution comes from a key observation about the nature of the 'valid' subsequence condition. The condition `(sub[i] + sub[i+1]) % 2` being constant only depends on the parities of the numbers. This simplifies the problem into finding the longest subsequence that follows one of four simple parity patterns. We can calculate the maximum length for each of these patterns greedily in a single pass and return the overall maximum.
**Time:** O(N), where N is the number of elements in `nums`. We iterate through the array once to calculate all necessary values. · **Space:** O(1), as we only use a constant number of variables to store counts and lengths, regardless of the input size.
**Pros:** Optimal time and space complexity.; Simple and elegant implementation once the underlying logic is understood.; Processes the input in a single pass.
**Cons:** Requires a key insight into the problem's structure, which might not be immediately obvious.
### Explanation
A deep look at the validity condition `(a + b) % 2 == k` reveals two main scenarios:

1.  **`k = 0`**: The sum of two numbers is even if they have the same parity (both even or both odd). Therefore, a valid subsequence of this type must consist entirely of even numbers or entirely of odd numbers. The longest such subsequence is simply the one with more elements, so its length is `max(total_even_numbers, total_odd_numbers)`. 

2.  **`k = 1`**: The sum of two numbers is odd if they have different parities (one even, one odd). Therefore, a valid subsequence of this type must have alternating parities. There are two possibilities: starting with an even number (`even, odd, even, ...`) or starting with an odd number (`odd, even, odd, ...`).

We can find the maximum length for all four of these patterns by iterating through the input array just once. We maintain counters for the total number of even and odd elements. Simultaneously, we greedily construct the two types of alternating subsequences, keeping track of their current lengths and the parity we expect next. The final answer is the maximum of these four computed lengths.

```java
class Solution {
    public int maximumLength(int[] nums) {
        int evenCount = 0;
        int oddCount = 0;
        
        // Length of alternating subsequence starting with even
        int altLenEvenStart = 0;
        int nextParityForEvenStart = 0; // 0 for even

        // Length of alternating subsequence starting with odd
        int altLenOddStart = 0;
        int nextParityForOddStart = 1; // 1 for odd

        for (int num : nums) {
            int parity = num % 2;

            // Count total evens and odds for same-parity subsequences
            if (parity == 0) {
                evenCount++;
            } else {
                oddCount++;
            }

            // Greedily build alternating subsequence starting with even
            if (parity == nextParityForEvenStart) {
                altLenEvenStart++;
                nextParityForEvenStart = 1 - nextParityForEvenStart;
            }

            // Greedily build alternating subsequence starting with odd
            if (parity == nextParityForOddStart) {
                altLenOddStart++;
                nextParityForOddStart = 1 - nextParityForOddStart;
            }
        }

        int maxLen = Math.max(evenCount, oddCount);
        maxLen = Math.max(maxLen, altLenEvenStart);
        maxLen = Math.max(maxLen, altLenOddStart);

        return maxLen;
    }
}
```
### Algorithm
- The problem can be broken down by analyzing the parity condition `(a + b) % 2`.
- **Case 1: Constant sum parity is 0.** This requires `a % 2 == b % 2`. The subsequence must be composed of all even or all odd numbers. The maximum length is `max(count of evens, count of odds)`.
- **Case 2: Constant sum parity is 1.** This requires `a % 2 != b % 2`. The subsequence must have alternating parities.
  - Subcase 2a: Starts with an even number (`even, odd, even, ...`).
  - Subcase 2b: Starts with an odd number (`odd, even, odd, ...`).
- We can calculate the lengths for these four possibilities in a single pass.
- Initialize counters: `evenCount`, `oddCount`, `altEvenStartLen`, `altOddStartLen` to 0.
- Initialize expected parities for the alternating cases: `nextParityEven = 0`, `nextParityOdd = 1`.
- Iterate through `nums`:
  - Update `evenCount` and `oddCount`.
  - Greedily build the alternating subsequences by checking the current number's parity against the expected parities and updating their lengths and next expected parities if they match.
- The final answer is the maximum of the four calculated lengths.

# Solutions
### Java

```java
class Solution {
public
  int maximumLength(int[] nums) {
    int k = 2;
    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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumLength(vector<int> &nums) {
    int k = 2;
    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;
  }
};

```

### Python

```python
class Solution:
    def maximumLength(self, nums: List[int]) -> int: k = 2 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

```