We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Maximum Length of Valid Subsequence I

Difficulty: Medium

Problem Description

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.

Key Insights

  • A valid subsequence must have all adjacent pairs that yield the same parity (even or odd).
  • The longest valid subsequence can be formed by combining all even and all odd numbers.
  • The total length of the longest valid subsequence will be the maximum of the count of even numbers and the count of odd numbers.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input array nums.
Space Complexity: O(1), since only a few variables are used to store counts.

Solution

To solve the problem, we can iterate through the given array and count how many even and odd numbers there are. Since a valid subsequence can consist of either all even numbers or all odd numbers, the length of the longest valid subsequence will be the maximum of these two counts.

Code Solutions

def maxLengthValidSubsequence(nums):
    even_count = 0
    odd_count = 0
    
    for num in nums:
        if num % 2 == 0:
            even_count += 1
        else:
            odd_count += 1
            
    return max(even_count, odd_count)

# Example Usage
print(maxLengthValidSubsequence([1, 2, 3, 4])) # Output: 4
print(maxLengthValidSubsequence([1, 2, 1, 1, 2, 1, 2])) # Output: 6
← Back to All Questions