Problem of The Day: Find the Maximum Length of Valid Subsequence I

Problem Statement

leetcode problem link

Brute Force [TLE]

Memoization Attempt

from collections import defaultdict
from typing import List

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        N = len(nums)
        memo = defaultdict(int)

        def dfs(i: int, parity: int, length: int) -> int:
            key = (i, parity, length)
            if key in memo:
                return memo[key]

            max_len = length
            for j in range(i + 1, N):
                next_parity = (nums[i] + nums[j]) % 2
                if next_parity == parity:
                    max_len = max(max_len, dfs(j, parity, length + 1))

            memo[key] = max_len
            return max_len

        max_length = 0
        for i in range(N - 1):
            for j in range(i + 1, N):
                parity = (nums[i] + nums[j]) % 2
                max_length = max(max_length, dfs(j, parity, 2))  # Start with a pair

        return max_length

DP Approach Attempt

from typing import List

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[1] * 2 for _ in range(n)]  # dp[i][0] for even parity chain, dp[i][1] for odd parity chain
        max_len = 1

        for i in range(n):
            for j in range(i):
                parity = (nums[i] + nums[j]) % 2
                dp[i][parity] = max(dp[i][parity], dp[j][parity] + 1)
                max_len = max(max_len, dp[i][parity])

        return max_len if max_len >= 2 else 0  # Only count chains with 2+ elements

Editorial

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        res = 0
        for pattern in [[0, 0], [0, 1], [1, 0], [1, 1]]:
            cnt = 0
            for num in nums:
                if num % 2 == pattern[cnt % 2]:
                    cnt += 1
            res = max(res, cnt)
        return res