最长定差子序列

我将为您讲解"最长定差子序列"这道线性动态规划题目。

题目描述
给定一个整数数组arr和一个整数difference，找出arr中最长的等差子序列的长度，其中等差数列的公差等于给定的difference。

例如：
输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是[7,5,3,1]，公差为-2

解题思路
这是一个经典的线性动态规划问题。我们需要找到最长的子序列，使得相邻元素之间的差值正好等于给定的difference。

详细解题步骤

步骤1：定义状态
我们定义dp[i]表示以arr[i]结尾的最长等差子序列的长度。

步骤2：状态转移方程
对于每个位置i，我们需要找到前面所有满足arr[j] = arr[i] - difference的位置j，然后在这些位置中选择dp值最大的那个。

状态转移方程为：
dp[i] = max(dp[j] + 1)，其中j < i且arr[j] = arr[i] - difference

如果找不到这样的j，那么dp[i] = 1

步骤3：优化状态转移
直接使用上述状态转移方程的时间复杂度是O(n²)，我们可以用哈希表来优化：

使用哈希表freq，其中freq[x]表示以数值x结尾的最长等差子序列的长度。

对于每个元素arr[i]：

• 查找前一个元素prev = arr[i] - difference
• 如果prev在哈希表中，dp[i] = freq[prev] + 1
• 否则，dp[i] = 1
• 更新freq[arr[i]] = max(freq[arr[i]], dp[i])

步骤4：算法实现

def longestSubsequence(arr, difference):
    dp = {}  # 哈希表，存储以每个数值结尾的最长子序列长度
    max_length = 0
    
    for num in arr:
        # 查找前一个元素是否存在
        prev = num - difference
        if prev in dp:
            dp[num] = dp[prev] + 1
        else:
            dp[num] = 1
        
        max_length = max(max_length, dp[num])
    
    return max_length

步骤5：示例分析
以arr = [1,5,7,8,5,3,4,2,1], difference = -2为例：

• 处理1：dp[1] = 1
• 处理5：dp[5] = 1 (5-(-2)=7不在dp中)
• 处理7：dp[7] = 1 (7-(-2)=9不在dp中)
• 处理8：dp[8] = 1 (8-(-2)=10不在dp中)
• 处理5：dp[5] = 1 (5已存在，但5-(-2)=7不在dp中，保持1)
• 处理3：dp[3] = dp[5] + 1 = 2 (3-(-2)=5在dp中)
• 处理4：dp[4] = 1 (4-(-2)=6不在dp中)
• 处理2：dp[2] = dp[4] + 1 = 2 (2-(-2)=4在dp中)
• 处理1：dp[1] = dp[3] + 1 = 3 (1-(-2)=3在dp中)

最终找到最长子序列长度为4（对应序列[7,5,3,1]）

步骤6：复杂度分析

• 时间复杂度：O(n)，只需要遍历数组一次
• 空间复杂度：O(n)，哈希表最多存储n个键值对

关键点总结

1. 使用哈希表记录以每个数值结尾的最长子序列长度
2. 对于每个元素，只需要检查前一个元素（当前值-difference）是否出现过
3. 这种方法将时间复杂度从O(n²)优化到O(n)

这个解法巧妙地利用了哈希表来避免双重循环，是线性动态规划中空间换时间的典型应用。