Problem Statement

• LeetCode 3201: Find the Maximum Length of Valid Subsequence I

Given an array of integers nums, find the maximum length of a valid subsequence. A valid subsequence is defined as one where all elements have the same parity (all even or all odd) OR the elements alternate between even and odd parities.

Algorithm Walkthrough

The solution uses a greedy approach to find the maximum length among three possible valid subsequences:

1. All Even Elements: Count all even numbers in the array
2. All Odd Elements: Count all odd numbers in the array
3. Alternating Parity: Build the longest subsequence that alternates between even and odd

Key Insight for Alternating Subsequence:

• Start with the parity of the first element (c = nums[0] % 2)
• Iterate through the array and greedily select elements that match the expected parity
• After selecting an element, flip the expected parity (c = 1 - c)
• This greedy approach works because we want the longest possible alternating sequence

Step-by-step execution:

nums = [1, 2, 3, 4, 5]
Initial: c = 1 (odd), alternate = 0

i=0: nums[0]=1, 1%2=1, matches c=1 → alternate=1, c=0 (now expect even)
i=1: nums[1]=2, 2%2=0, matches c=0 → alternate=2, c=1 (now expect odd)  
i=2: nums[2]=3, 3%2=1, matches c=1 → alternate=3, c=0 (now expect even)
i=3: nums[3]=4, 4%2=0, matches c=0 → alternate=4, c=1 (now expect odd)
i=4: nums[4]=5, 5%2=1, matches c=1 → alternate=5, c=0

Final counts: even=2, odd=3, alternate=5
Result: max(5, max(2, 3)) = 5

Complexity Analysis

Time Complexity: O(n)

• Single pass through the array to count elements and build alternating subsequence
• All operations inside the loop are O(1)

Space Complexity: O(1)

• Only using a constant amount of extra variables (even, odd, alternate, c)
• No additional data structures needed

Full Solution (Java)

class Solution {
    public int maximumLength(int[] nums) {
        int n = nums.length;
        int c = nums[0] % 2;  // Expected parity for alternating sequence
        int even = 0;         // Count of even numbers
        int odd = 0;          // Count of odd numbers  
        int alternate = 0;    // Length of alternating sequence

        for (int i = 0; i < n; i++) {
            int curNum = nums[i];

            // Count even and odd numbers
            if (curNum % 2 == 0) {
                even++;
            } else {
                odd++;
            }

            // Build alternating subsequence greedily
            if (curNum % 2 == c) {
                alternate++;
                c = 1 - c;  // Flip expected parity
            }
        }

        // Return maximum of all three possibilities
        return Math.max(alternate, Math.max(even, odd));
    }
}

The solution elegantly handles all three cases in a single pass, making it both time and space efficient.