#3201

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Find the Maximum Length of Valid Subsequence I

Find the longest valid subsequence in an array of integers using dynamic programming to handle different patterns of sequence formation.

array dynamic programming

Problem Statement

You are given an array of integers. A subsequence of this array is considered valid if it follows one of these four patterns: all even elements, all odd elements, alternating even-odd elements, or alternating odd-even elements. You need to return the length of the longest valid subsequence that can be formed.

A subsequence is derived by removing some or no elements from the array without changing the order of the remaining elements. For example, for the array [1,2,3,4], the longest valid subsequence could be [1,2,3,4] itself.

Examples

Example 1

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

Output: 4

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

Example 2

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

Output: 6

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

Example 3

Input: nums = [1,3]

Output: 2

The longest valid subsequence is [1, 3] .

Constraints

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

Solution Approach

State Transition Dynamic Programming

The problem can be solved using dynamic programming by considering the possible subsequence patterns. For each element, track the longest subsequence that ends with either an odd or an even number. Depending on the current number's parity, transition the state from the previous subsequences accordingly.

Two Pointer or Sliding Window Technique

Alternatively, use a two-pointer technique to traverse through the array and track subsequences that follow one of the valid patterns. Adjust the pointers dynamically to ensure subsequences are valid and track the maximum length.

Greedy Approach for Pattern Matching

A greedy solution can be used to check each subsequence pattern, maximizing the length by alternating between odd and even numbers or focusing on subsequences with all even or all odd numbers.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity of the solution is O(n), as we traverse the array once. The space complexity is O(1), as we only need a few variables to track the maximum subsequence length.

What Interviewers Usually Probe

Look for familiarity with dynamic programming and state transitions.
Check if the candidate understands subsequence patterns and edge cases.
Observe how the candidate handles different subsequences' parity and alternating patterns.

Common Pitfalls or Variants

Common pitfalls

Confusing the subsequence with a subarray, which requires contiguous elements.
Forgetting to properly alternate between odd and even elements in valid subsequences.
Not properly handling arrays with mixed parity that require alternating patterns.

Follow-up variants

Consider the case when all numbers are the same.
What if the array contains only even or only odd numbers?
How does the solution scale with the maximum array size?

FAQ

What is the primary pattern used to solve the "Find the Maximum Length of Valid Subsequence I" problem?

The primary pattern is state transition dynamic programming, where you track subsequences based on parity (odd/even) and possible alternating patterns.

What are the possible patterns for a valid subsequence?

The valid subsequences can either be all even elements, all odd elements, alternating even-odd elements, or alternating odd-even elements.

How does the dynamic programming approach work for this problem?

The dynamic programming approach works by maintaining the length of valid subsequences for odd and even elements, and updating these lengths as you move through the array.

What is the time complexity of solving this problem?

The time complexity is O(n) because we traverse the array only once, making state transitions based on each element.

Can a greedy approach work for this problem?

Yes, a greedy approach can be used to find the longest subsequence by alternating between odd and even elements, or focusing on subsequences with all odd or all even numbers.

terminal

Solution

Solution 1: Dynamic Programming

We set $k = 2$.

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#3202 find the maximum length of valid subsequence ii #3196 maximize total cost of alternating subarrays #3193 count the number of inversions