Watch 10 video solutions for Find the Maximum Length of Valid Subsequence I, a medium level problem involving Array, Dynamic Programming. This walkthrough by codestorywithMIK has 13,453 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 * 1051 <= nums[i] <= 107Problem Overview: You are given an integer array. The task is to select a subsequence such that the parity of every adjacent pair sum stays the same. In other words, for every adjacent pair (a[i], a[i+1]) in the subsequence, the value of (a[i] + a[i+1]) % 2 must remain constant. The goal is to return the maximum possible length of such a subsequence.
Approach 1: Greedy Approach with Pairwise Checking (O(n) time, O(1) space)
The key observation comes from parity. If (a + b) % 2 = 0, both numbers have the same parity. If (a + b) % 2 = 1, they have different parity. That means a valid subsequence must either keep the same parity for every element (all even or all odd) or strictly alternate between even and odd. Iterate through the array and count how many even and odd numbers exist. The best same-parity subsequence is simply the larger of the two counts. For the alternating case, you greedily construct a subsequence by switching parity whenever possible. The maximum valid length becomes the best result among these options.
Approach 2: Dynamic Programming with State Tracking (O(n) time, O(1) space)
This method explicitly models the constraint using dynamic programming. Track states based on the parity of the last chosen element and the required parity of the pair sum. For each number, compute its parity and update states that represent extending a subsequence with the same sum parity. The transition checks whether (prev + current) % 2 matches the required pattern. Because parity only has two values, the DP state space remains constant. This approach is useful when generalizing to more complex constraints or when building intuition for subsequence state transitions.
Both solutions rely heavily on parity properties and sequential processing of the array, a common pattern in array problems and subsequence optimization tasks. The greedy approach derives directly from parity behavior, while the DP formulation makes the constraint explicit and easier to reason about.
Recommended for interviews: The greedy parity-counting insight is what most interviewers expect. It shows you recognized that the pair constraint collapses into parity patterns. Explaining the DP state formulation first demonstrates problem decomposition, then simplifying it into the greedy counting solution shows strong optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Approach with Pairwise Checking | O(n) | O(1) | Best for production and interviews. Uses parity counting and simple iteration. |
| Dynamic Programming with State Tracking | O(n) | O(1) | Useful for understanding subsequence transitions and generalizing similar DP problems. |