[Leetcode] 3201. Find the Maximum Length of Valid Subsequence I

https://leetcode.com/problems/find-the-maximum-length-of-valid-subsequence-i/?envType=daily-question&envId=2025-07-16

initial

It was wrong i was just checking the consecutive elements via

        for i in range(1,length):
            ans[i]=(nums[i]+nums[i-1])%2

which doesnt consider the nature of "subsequence". So if u have example like [1,5,9,4,2], my ans list was giving [0, 0, 0, 1, 0] and thus value 4 as answer but correct answer is 3, where [1,5,9] is the ans. I was just blindly counting zeros and ones.

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        length = len(nums)
        ans = [0 for _ in range(length)]
        for i in range(1,length):
            ans[i]=(nums[i]+nums[i-1])%2
        count_zero=0
        count_one=0
        for i in range(1,length):
            if ans[i]:
                count_one+=1
            else:
                count_zero+=1
        print(ans)
        return max(count_zero,count_one)+1
       

sol

Instead this q can be split to 4 patterns, which i also thought of. its either all even or odd, or alternating odds and evens.

So for the first 2, its ez we just count number of 0s and 1s. But for alternating we should use dp where

if cur num is 1, that means we can take the length of subsequence that ends with 0 and increment by 1 cuz we can extend this alternating subsequence. Else, we can just start a new subsequence here. So dp formula is

dp_odd_length = max(dp_even_length+1, 1)

same for even

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        length = len(nums)
        tmp = [num%2 for num in nums]
        count_zero=tmp.count(0)
        count_one=tmp.count(1)
        dp_even_length,dp_odd_length=0,0
        for i in range(length):
            ## odd
            if tmp[i]:
                dp_odd_length = max(dp_even_length+1, 1)
            else:
                dp_even_length = max(dp_odd_length+1,1)
        return max(max(dp_odd_length,dp_even_length), max(count_zero,count_one))

complexity

n time
n space