JZX轻语：简

LeetCode 1218 - 最长定差子序列

发表于2024年07月09日

定义dp[i]为以数字i(注意不是以下标i结尾)结尾的最长定差子序列的长度(用哈希表维护dp)。对于每个数字num，如果num - difference在哈希表中，那么dp[num] = dp[num - difference] + 1，否则dp[num] = 1。最后返回哈希表中的最大值即可。

为啥无需dp[num] = max(dp[num], dp[num - difference] + 1)呢？不妨使用反证法，如果先前的dp[num]大于dp[num - difference] + 1，即先前的dp[num] - 1大于dp[num - difference]，意味着先前的以num - difference结尾的长度比现在的还要大，与dp[num - difference]是以num - difference结尾的最长定差子序列的长度矛盾。

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = {}
        ans = 0
        for num in arr:
            dp[num] = 1 + dp.get(num - difference, 0)
            ans = max(ans, dp[num])
        return ans