线性动态规划：最长定差子序列 题目描述 给定一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于给定的 difference。 例如： 输入：arr = [ 1,2,3,4 ], difference = 1 输出：4 解释：最长的等差子序列是 [ 1,2,3,4 ] 解题过程 1. 问题分析 我们需要找到最长的等差子序列，其中相邻元素的差固定为 difference。注意这里说的是子序列（不要求连续），而不是子数组（要求连续）。 关键观察： 对于每个元素 arr[ i ]，我们想知道以它结尾的最长等差子序列长度 如果存在前一个元素 prev = arr[ i] - difference，那么我们可以将 arr[ i ] 接在以 prev 结尾的子序列后面 这提示我们可以使用动态规划来记录状态 2. 状态定义 定义 dp[ x ] 表示以数值 x 结尾的最长等差子序列的长度。 但是直接使用数值作为下标可能不现实，因为数组元素范围可能很大。我们可以使用哈希表来存储状态。 3. 状态转移方程 对于每个元素 arr[ i ]： 前一个元素应该是 prev = arr[ i ] - difference 如果 prev 在之前出现过（即在我们的状态记录中存在），那么： dp[ arr[ i]] = dp[ prev ] + 1 如果 prev 没出现过，那么 arr[ i ] 自己构成一个长度为 1 的子序列： dp[ arr[ i] ] = 1 4. 算法步骤 让我们用例子 arr = [ 1,5,7,8,5,3,4,2,1 ], difference = -2 来演示： 初始化：创建一个空的哈希表 dp，用于记录状态 max_ len = 0 # 记录最终答案 遍历过程： i=0, arr[ 0]=1: prev=1-(-2)=3，3不在dp中，dp[ 1 ]=1 i=1, arr[ 1]=5: prev=5-(-2)=7，7不在dp中，dp[ 5 ]=1 i=2, arr[ 2]=7: prev=7-(-2)=9，9不在dp中，dp[ 7 ]=1 i=3, arr[ 3]=8: prev=8-(-2)=10，10不在dp中，dp[ 8 ]=1 i=4, arr[ 4]=5: prev=5-(-2)=7，7在dp中且dp[ 7]=1，dp[ 5]=dp[ 7 ]+1=2 i=5, arr[ 5]=3: prev=3-(-2)=5，5在dp中且dp[ 5]=2，dp[ 3]=dp[ 5 ]+1=3 i=6, arr[ 6]=4: prev=4-(-2)=6，6不在dp中，dp[ 4 ]=1 i=7, arr[ 7]=2: prev=2-(-2)=4，4在dp中且dp[ 4]=1，dp[ 2]=dp[ 4 ]+1=2 i=8, arr[ 8]=1: prev=1-(-2)=3，3在dp中且dp[ 3]=3，dp[ 1]=dp[ 3 ]+1=4 最终找到的最长子序列是 [ 1,3,5,7 ]，长度为4。 5. 复杂度分析 时间复杂度：O(n)，只需要遍历数组一次 空间复杂度：O(n)，最坏情况下需要存储所有不同的数值 6. 关键点总结 使用哈希表来记录以每个数值结尾的最长子序列长度 对于每个元素，查找是否存在前驱元素 arr[ i ] - difference 动态更新最大值作为最终答案 这种方法巧妙地利用了哈希表来避免二维动态规划，将时间复杂度从 O(n²) 优化到 O(n)。