Find the Maximum Length of Valid Subsequence I

Find the Maximum Length of Valid Subsequence I

What is this problem about?

In the Find the Maximum Length of Valid Subsequence I coding problem, a subsequence is considered "valid" if the sum of every pair of adjacent elements in it has the same parity (either all sums are even or all sums are odd). You are given an array of integers and need to find the maximum length of such a valid subsequence.

Why is this asked in interviews?

Microsoft and Meta ask this to test your ability to simplify complex conditions into basic modular arithmetic. The condition "adjacent sums have the same parity" implies that the subsequence must follow a specific parity pattern:

1. All even: [E, E, E, ...] (Sums: E+E=E)
2. All odd: [O, O, O, ...] (Sums: O+O=E)
3. Alternating: [E, O, E, O, ...] or [O, E, O, E, ...] (Sums: E+O=O) It evaluations your proficiency with Dynamic Programming interview patterns or greedy selection based on state.

Algorithmic pattern used

This problem uses Greedy counting with Parity States.

1. Count all even numbers.
2. Count all odd numbers.
3. Find the longest alternating sequence starting with Even (E $o$ O $o$ E).
4. Find the longest alternating sequence starting with Odd (O $o$ E $o$ O). The answer is the maximum of these four counts. Since you only care about the last element's parity to decide the next one, this can be done in a single linear pass.

Example explanation

nums = [1, 2, 3, 4]

1. All Even: [2, 4] (Length 2).
2. All Odd: [1, 3] (Length 2).
3. Alternating (E-O-E): [2, 3] (Length 2).
4. Alternating (O-E-O): [1, 2, 3] (Length 3). Max length: 3.

Common mistakes candidates make

• Over-complicating with DP: Using a full $O(N^2)$ DP when $O(N)$ is possible.
• Missing alternating cases: Only checking for all-even or all-odd subsequences.
• Parity logic errors: Forgetting that Even + Odd = Odd and Even + Even = Even.

Interview preparation tip

When a problem involves "adjacent pairs" having a property, check if that property translates to a repeating pattern (like parity). Most subsequence problems with adjacent constraints can be reduced to a small number of states (in this case, 2 states: Even or Odd).