Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

If every adjacent-pair sum is even, all selected values have the same parity. If every sum is odd, selected parities alternate. These are the only possibilities, so compare all-even, all-odd, alternating-from-even, and alternating-from-odd subsequences.

Approach

Scan the array and count even and odd values. At the same time, maintain two alternating subsequence lengths and the next parity required by each, initially even for one and odd for the other. Whenever a value matches a required parity, accept it and flip that requirement.

Taking the earliest available matching parity cannot harm an alternating subsequence: it leaves at least as many later positions for the remaining choices as any later match would. Thus both greedy alternating scans find their best lengths. Return the largest of the four counts; each counted subsequence has a constant adjacent-sum parity, and every valid subsequence belongs to one of these patterns.

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        e, o, eo, oe = 0, 0, 0, 0
        req_eo, req_oe = 0, 1

        for x in nums:
            x %= 2
            if x == 0:
                e += 1
            else:
                o += 1
            if x == req_eo:
                eo += 1
                req_eo ^= 1
            if x == req_oe:
                oe += 1
                req_oe ^= 1

        return max(e, o, eo, oe)

Complexity analysis

Let n = nums.length. Time: O(n). Auxiliary space: O(1).