LC-3202 Medium LeetCode

3202. Find the Maximum Length of Valid Subsequence II

Read the full problem statement on LeetCode.

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

Reading material

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

Reference solution (spoiler · python)

# Time:  O(n * k)
# Space: O(k)

# dp
class Solution(object):
    def maximumLength(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        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

Solution from kamyu104/LeetCode-Solutions · MIT