[Leetcode] 3202. Find the Maximum Length of Valid Subsequence II (retry)

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

initial

coming from https://velog.io/@whitehousechef/Leetcode-3201.-Find-the-Maximum-Length-of-Valid-Subsequence-I

its quite hard. We need to know this math logic where

lets say we are iterating and have curNum. We wanna track all possible remainders from 0 to k-1 so we need dp table that tracks each remainder. For this curNum, we wanna extend a previous subsequence which has a remainder that when that previous remainder and current remainder is added, it is equal to a target remainder (0 to k-1), which we call it mod.

For example
(a + b) % k == (b + c) % k == (c + d) % k == ...
If (a + b) % k == mod, and we want to extend with c
We need (b + c) % k == mod
Which means b % k must equal (mod - c % k + k) % k. So we dont care about numbers but the remainders mattter.

(curNum + prevNum) % k = mod
prevNum = (mod - curNum +k)%k
the + k is needed to handle negative modulo

So we are looking for a previous subsequence that has this prevNum.

We can represent dp[curNum][mod] as max length of subsequence ending with number (curNum) and this subsequence has pairs that have sum remainder of mod.

dp[curNum][mod] = max(dp[curNum][mod], dp[prevNum][mod] +1)

For each number curNum:
curRemainder = curNum % k

For each target_mod from 0 to k-1:
    // What remainder should the previous number have?
    prevRemainder = (target_mod - curRemainder + k) % k
    
    // Extend the best subsequence ending with prevRemainder
    newLength = dp[prevRemainder][target_mod] + 1
    
    // Update the best subsequence ending with curRemainder
    dp[curRemainder][target_mod] = max(dp[curRemainder][target_mod], newLength)

sol

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        ## for current element to extend previous subsequence with target remainder (mod)
        # (prevNum + curNum) % k = mod
        # prevNum = (mod-curNum +k)%k
        dp=[[0 for _ in range(k)] for _ in range(k)]
        ans=0
        for i in range(len(nums)):
            curNum = nums[i]%k
            # mod is target remainder
            for mod in range(k):
                prevNum = (mod-curNum +k)%k
                dp[curNum][mod]=max(dp[curNum][mod], dp[prevNum][mod]+1)
                ans=max(dp[curNum][mod],ans)
        return ans

complexity

nk time
k^2 space