发表于 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

• LC 题目链接