LC-3201 Medium LeetCode

3201. Find the Maximum Length of Valid Subsequence I

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 38% Topics: Array, Dynamic Programming

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

# dp
class Solution(object):
    def maximumLength(self, nums):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        k = 2
        result = 0
        for i in xrange(k):
            dp = [0]*k
            for x in nums:
                dp[x%k] = dp[(i-x)%k]+1
            result = max(result, max(dp))
        return result


# Time:  O(n)
# Space: O(1)
# brute force
class Solution2(object):
    def maximumLength(self, nums):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return max(sum(x%2 == 0 for x in nums),
                   sum(x%2 == 1 for x in nums),
                   sum(nums[i]%2 != nums[i+1]%2 for i in xrange(len(nums)-1))+1)

Solution from kamyu104/LeetCode-Solutions · MIT