Find the Maximum Length of Valid Subsequence I

• Create a recursive function, for example, generate(index, currentSubsequence), to explore all possibilities.
• The function will have two recursive calls for each element nums[index]:
  1. One call that excludes nums[index] from the subsequence.
  2. Another call that includes nums[index] in the subsequence.
• The base case for the recursion is when index reaches the end of the array nums.
• In the base case, check if the currentSubsequence is valid. A subsequence sub is valid if the parity of the sum of adjacent elements, (sub[i] + sub[i+1]) % 2, is constant for all i.
• Maintain a global variable to keep track of the maximum length of a valid subsequence found so far.
• Since any subsequence of length less than 2 is trivially valid, and the constraints guarantee nums.length >= 2, the answer will be at least 2.

The core of this method is a backtracking algorithm. We can define a recursive helper function that builds subsequences element by element. For each element in the original array, we decide whether to include it in our current subsequence or not. This branching creates a decision tree that covers all 2^N possible subsequences.

When the recursion reaches the end of the input array, we have a complete subsequence. We then pass this subsequence to a validation function. The validation function checks if the subsequence has a length of at least 2. If it does, it calculates the parity of the sum of the first two elements, (sub[0] + sub[1]) % 2. It then iterates through the rest of the adjacent pairs, ensuring they all yield the same sum parity. If the subsequence is valid, we update our global maximum length. While simple to conceptualize, the sheer number of subsequences makes this approach impractical for the given constraints.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    int maxLength = 0;6 7    public int maximumLength(int[] nums) {8        // Any subsequence of length 1 is valid. Since nums.length >= 2, we can find a pair.9        // The smallest non-trivial valid subsequence has length 2.10        // We can initialize maxLength to 0, and it will be updated.11        generateSubsequences(nums, 0, new ArrayList<>());12        return maxLength;13    }14 15    private void generateSubsequences(int[] nums, int index, List<Integer> currentSub) {16        if (index == nums.length) {17            if (isValid(currentSub)) {18                maxLength = Math.max(maxLength, currentSub.size());19            }20            return;21        }22 23        // Decision 1: Exclude nums[index]24        generateSubsequences(nums, index + 1, currentSub);25 26        // Decision 2: Include nums[index]27        currentSub.add(nums[index]);28        generateSubsequences(nums, index + 1, currentSub);29        currentSub.remove(currentSub.size() - 1); // Backtrack30    }31 32    private boolean isValid(List<Integer> sub) {33        if (sub.size() < 2) {34            return true; // Vacuously true, length will be 0 or 1.35        }36        int expectedParity = (sub.get(0) + sub.get(1)) % 2;37        for (int i = 1; i < sub.size() - 1; i++) {38            if ((sub.get(i) + sub.get(i + 1)) % 2 != expectedParity) {39                return false;40            }41        }42        return true;43    }44}

• Initialize two DP arrays, dp_same and dp_alt, both of size n and filled with 1s. dp_same[i] will store the length of the longest same-parity subsequence ending at nums[i], and dp_alt[i] for alternating-parity.
• Iterate with an outer loop for i from 0 to n-1.
• Inside, have an inner loop for j from 0 to i-1.
• In the inner loop, compare the parities of nums[i] and nums[j].
  • If (nums[i] % 2) == (nums[j] % 2), it means they can extend a same-parity subsequence. Update dp_same[i] = max(dp_same[i], 1 + dp_same[j]).
  • If their parities are different, they can extend an alternating-parity subsequence. Update dp_alt[i] = max(dp_alt[i], 1 + dp_alt[j]).
• After the inner loop, update a variable maxLen with the maximum value seen so far in dp_same[i] and dp_alt[i].
• Return maxLen after the loops complete.

This method is based on the classic Longest Increasing Subsequence (LIS) problem structure. We can categorize the valid subsequences into two types:

1. Those where all elements have the same parity (e.g., all even or all odd).
2. Those where elements have alternating parities (e.g., even, odd, even, ...).

We can use two DP arrays to track the lengths of these two types of subsequences. Let dp_same[i] be the length of the longest same-parity subsequence ending with nums[i], and dp_alt[i] be the length of the longest alternating-parity subsequence ending with nums[i]. To calculate dp_same[i], we find a j < i such that nums[j] has the same parity as nums[i] and dp_same[j] is maximized. Then, dp_same[i] = 1 + dp_same[j]. A similar logic applies to dp_alt[i], but we look for nums[j] with a different parity. The overall answer is the maximum value found across both DP arrays.

1import java.util.Arrays;2 3class Solution {4    public int maximumLength(int[] nums) {5        int n = nums.length;6        if (n <= 2) {7            return n;8        }9 10        // dp_same[i]: length of longest subsequence with same parity ending at index i11        int[] dp_same = new int[n];12        // dp_alt[i]: length of longest subsequence with alternating parity ending at index i13        int[] dp_alt = new int[n];14        Arrays.fill(dp_same, 1);15        Arrays.fill(dp_alt, 1);16 17        int maxLen = 1;18 19        for (int i = 0; i < n; i++) {20            for (int j = 0; j < i; j++) {21                if ((nums[i] % 2) == (nums[j] % 2)) {22                    dp_same[i] = Math.max(dp_same[i], 1 + dp_same[j]);23                } else {24                    dp_alt[i] = Math.max(dp_alt[i], 1 + dp_alt[j]);25                }26            }27            maxLen = Math.max(maxLen, Math.max(dp_same[i], dp_alt[i]));28        }29 30        return maxLen;31    }32}

• The problem can be broken down by analyzing the parity condition (a + b) % 2.
• Case 1: Constant sum parity is 0. This requires a % 2 == b % 2. The subsequence must be composed of all even or all odd numbers. The maximum length is max(count of evens, count of odds).
• Case 2: Constant sum parity is 1. This requires a % 2 != b % 2. The subsequence must have alternating parities.
  • Subcase 2a: Starts with an even number (even, odd, even, ...).
  • Subcase 2b: Starts with an odd number (odd, even, odd, ...).
• We can calculate the lengths for these four possibilities in a single pass.
• Initialize counters: evenCount, oddCount, altEvenStartLen, altOddStartLen to 0.
• Initialize expected parities for the alternating cases: nextParityEven = 0, nextParityOdd = 1.
• Iterate through nums:
  • Update evenCount and oddCount.
  • Greedily build the alternating subsequences by checking the current number's parity against the expected parities and updating their lengths and next expected parities if they match.
• The final answer is the maximum of the four calculated lengths.

A deep look at the validity condition (a + b) % 2 == k reveals two main scenarios:

1. k = 0: The sum of two numbers is even if they have the same parity (both even or both odd). Therefore, a valid subsequence of this type must consist entirely of even numbers or entirely of odd numbers. The longest such subsequence is simply the one with more elements, so its length is max(total_even_numbers, total_odd_numbers).

2. k = 1: The sum of two numbers is odd if they have different parities (one even, one odd). Therefore, a valid subsequence of this type must have alternating parities. There are two possibilities: starting with an even number (even, odd, even, ...) or starting with an odd number (odd, even, odd, ...).

We can find the maximum length for all four of these patterns by iterating through the input array just once. We maintain counters for the total number of even and odd elements. Simultaneously, we greedily construct the two types of alternating subsequences, keeping track of their current lengths and the parity we expect next. The final answer is the maximum of these four computed lengths.

1class Solution {2    public int maximumLength(int[] nums) {3        int evenCount = 0;4        int oddCount = 0;5        6        // Length of alternating subsequence starting with even7        int altLenEvenStart = 0;8        int nextParityForEvenStart = 0; // 0 for even9 10        // Length of alternating subsequence starting with odd11        int altLenOddStart = 0;12        int nextParityForOddStart = 1; // 1 for odd13 14        for (int num : nums) {15            int parity = num % 2;16 17            // Count total evens and odds for same-parity subsequences18            if (parity == 0) {19                evenCount++;20            } else {21                oddCount++;22            }23 24            // Greedily build alternating subsequence starting with even25            if (parity == nextParityForEvenStart) {26                altLenEvenStart++;27                nextParityForEvenStart = 1 - nextParityForEvenStart;28            }29 30            // Greedily build alternating subsequence starting with odd31            if (parity == nextParityForOddStart) {32                altLenOddStart++;33                nextParityForOddStart = 1 - nextParityForOddStart;34            }35        }36 37        int maxLen = Math.max(evenCount, oddCount);38        maxLen = Math.max(maxLen, altLenEvenStart);39        maxLen = Math.max(maxLen, altLenOddStart);40 41        return maxLen;42    }43}