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

Problem Statement

leetcode problem link

Brute Force [TLE]

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

        def dfs(start, curr, length):
            key = (start, curr, length)

            if key in memo:
                return memo[key]

            max_len = length
            for i in range(start + 1, N):
                next_val = (nums[i] + nums[start]) % k
                if next_val == curr:
                    max_len = max(max_len, dfs(i, curr, length + 1))

            memo[key] = max_len
            return max_len

        max_length = 0
        for i in range(N):
            for j in range(i + 1, N):
                val = (nums[i] + nums[j]) % k
                max_length = max(max_length, dfs(j, val, 2))

        return max_length

Editorial

DP Approach

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        dp = [[0] * k for _ in range(k)]
        res = 0
        for num in nums:
            num %= k
            for prev in range(k):
                dp[prev][num] = dp[num][prev] + 1
                res = max(res, dp[prev][num])
        return res