1218.最长定差子序列

https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/

一、dp

求”最长”、“最短”这种，下意识用dp

用dp[i]表示arr中[0, i]部分最长定差子序列的长度，每次用j遍历[0, i-1]，若有arr[j] = arr[i] - d，则dp[i] = dp[j] + 1。

class Solution:
    def longestSubsequence(self, arr, difference) -> int:
        n = len(arr)
        dp = [1] * n
        res = 0
        for i in range(1, n):
            for j in range(0, i):
                if arr[j] == arr[i] - difference:
                    dp[i] = dp[j] + 1
            res = max(res, dp[i])
        return res

然而这样超时，复杂度O(n^2)。其实并没有利用好dp的性质，即从一个状态立即推出另一个状态，而不是求dp[i]还要循环遍历

改进

直接用dp[v]表示以v（元素值，而非下标）结尾的最长等差子序列长度， 为保证序列性，从前向后遍历，易知dp[v] = dp[v-d] + 1

初始情况为dp[v]=0，即v不在arr中

最后求dp[v]的最大值

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