Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3491. Find the Maximum Length of Valid Subsequence II

My accepted Python solution to LeetCode problem 3491, Find the Maximum Length of Valid Subsequence II, running in 1247ms.

  • Difficulty: Medium
  • Python
  • Runtime 1247ms
  • Memory 17.5MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 1247ms, memory 17.5MB, accepted 2026-01-01.

python
class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        # dp[r][prev_mod] = max length of valid subsequence ending with element having prev_mod
        # where (prev + current) % k == r
        
        result = 0
        
        # For each target remainder r, find the longest valid subsequence
        for r in range(k):
            # dp[m] = max length ending with an element whose value % k == m
            # and (prev + current) % k == r
            dp = [0] * k
            
            for num in nums:
                curr_mod = num % k
                # We need prev_mod such that (prev_mod + curr_mod) % k == r
                prev_mod = (r - curr_mod + k) % k
                
                dp[curr_mod] = dp[prev_mod] + 1
            
            result = max(result, max(dp))
        
        return result

Source