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] <= 107To find the longest valid subsequence, you can iterate through the list and keep track of the subsequence by maintaining the parity of consecutive pair sums. Start with the entire sequence and verify the condition iteratively, constructing valid subsequences as you proceed through the list.
This code iterates through the array and tracks the parity of sums of each consecutive pair, resetting the subsequence length when the condition is broken.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) — A single iteration through the array.
Space Complexity: O(1) — Constant space usage.
A dynamic programming approach can be used to track the longest subsequence lengths with different initial parities. Create a DP array where each entry keeps track of the longest subsequence ending at that index.
This DP approach assigns a dp[i] to calculate maximum subsequences ending at each index by checking against all previous indices to count valid pairs.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) — Looping through prior elements for validation.
Space Complexity: O(n) — Storing state for each element.
| Approach | Complexity |
|---|---|
| Greedy Approach with Pairwise Checking | Time Complexity: O(n) — A single iteration through the array. |
| Dynamic Programming with State Tracking | Time Complexity: O(n^2) — Looping through prior elements for validation. |
Leetcode 128 - LONGEST CONSECUTIVE SEQUENCE • NeetCode • 455,447 views views
Watch 9 more video solutions →Practice Find the Maximum Length of Valid Subsequence I with our built-in code editor and test cases.
Practice on FleetCode