arr = [1, 5, 7, 8, 5, 3, 4, 2, 1]
difference = -2

dp[arr[i]] = dp[arr[i] - difference] + 1

最长定差子序列的长度与个数（进阶版：统计所有最长定差子序列的个数，并记录每个最长子序列的具体序列） 题目描述 给定一个整数数组 arr 和一个整数 difference ，你需要找出数组中所有等差子序列中最长定差子序列的长度，并且还需要统计 所有最长定差子序列的个数 ，最后还要记录 每个最长定差子序列的具体序列 （即序列的值）。 定义 ：定差子序列是指一个序列中相邻两项的差等于给定的整数 difference ，子序列不要求连续，但必须保持原数组中的相对顺序。 示例 ： 在这个例子中，最长的定差子序列是 [7, 5, 3, 1] （差为 -2），长度为 4。我们需要找出所有这样的最长定差子序列，并记录它们的值。 解题思路 这个问题可以拆解为三个子目标： 找出最长定差子序列的 长度 。 统计所有最长定差子序列的 个数 。 记录每个最长定差子序列的 具体序列 。 步骤 1：基础的动态规划（求长度） 我们先从一个简单问题开始： 只求最长长度 。 设 dp[x] 表示以数字 x 结尾的最长定差子序列的长度。 对于数组中的每个数 arr[i] ，我们检查它前面的数 prev = arr[i] - difference 是否出现过，如果出现过，则 dp[arr[i]] = dp[prev] + 1 ，否则 dp[arr[i]] = 1 。 由于数字可能很大，我们用一个哈希表来存储 dp 值。 状态转移方程 ： 例子 ： arr = [1, 5, 7, 8, 5, 3, 4, 2, 1] , difference = -2 遍历过程： i=0, x=1: prev=3 不在表中，dp[ 1 ]=1 i=1, x=5: prev=7 不在表中，dp[ 5 ]=1 i=2, x=7: prev=9 不在表中，dp[ 7 ]=1 i=3, x=8: prev=10 不在表中，dp[ 8 ]=1 i=4, x=5: prev=7 在表中，dp[ 7]=1，所以 dp[ 5 ]=2 i=5, x=3: prev=5 在表中，dp[ 5]=2，所以 dp[ 3 ]=3 i=6, x=4: prev=6 不在表中，dp[ 4 ]=1 i=7, x=2: prev=4 在表中，dp[ 4]=1，所以 dp[ 2 ]=2 i=8, x=1: prev=3 在表中，dp[ 3]=3，所以 dp[ 1 ]=4 最终 dp 表中最大值是 4（以 1 结尾）。 结果 ：最长长度 = 4。 步骤 2：统计最长定差子序列的个数 现在不仅要长度，还要统计 有多少个不同的最长定差子序列 。 我们定义两个哈希表： len[x] ：以数字 x 结尾的最长定差子序列的长度。 cnt[x] ：以数字 x 结尾的、长度为 len[x] 的定差子序列的个数。 状态转移： 当遇到 arr[i] 时，计算前一个数 prev = arr[i] - difference 。 如果 prev 在表中： 新的长度 newLen = len[prev] + 1 如果 newLen > len[arr[i]] ： 更新 len[arr[i]] = newLen 更新 cnt[arr[i]] = cnt[prev] （因为现在以 arr[i] 结尾的最长子序列个数就等于以 prev 结尾的个数） 如果 newLen == len[arr[i]] ： 增加 cnt[arr[i]] += cnt[prev] 如果 prev 不在表中： 初始化 len[arr[i]] = 1 , cnt[arr[i]] = 1 同时，我们维护一个全局最长长度 maxLen 和对应的总个数 totalCnt 。 遍历过程中，每当更新 len[arr[i]] 时，如果它等于 maxLen ，则累加 cnt[arr[i]] 到 totalCnt ；如果它大于 maxLen ，则重置 totalCnt = cnt[arr[i]] 并更新 maxLen 。 步骤 3：记录具体的最长定差子序列 这是最复杂的部分。我们需要记录每个以数字 x 结尾的、长度为 len[x] 的所有子序列。 因为要存储具体序列，我们不能只存个数，而是要存一个列表的列表（或类似结构）。但直接存储会占用大量空间，尤其当数字很多时。 优化思路 ： 我们可以存储每个序列的“前驱指针”。 对于每个 (x, length) 对，我们存储所有能到达 (x, length) 的前一个数字 prev 的列表。 这样，我们可以从所有满足 len[x] == maxLen 的 x 开始，反向回溯构造出所有序列。 数据结构 ： len[x] 同上 prevMap[x][l] 可以是一个字典，键是长度 l，值是一个列表，存储所有能到达 (x, l) 的前一个数字 prev 。 具体步骤 ： 遍历数组，对于每个 arr[i] ，计算 prev = arr[i] - difference 。 如果 prev 在 len 中： newLen = len[prev] + 1 如果 newLen > len[arr[i]] ： 更新 len[arr[i]] = newLen 更新 prevMap[arr[i]][newLen] = [prev] （清空之前的，因为现在找到了更长的） 如果 newLen == len[arr[i]] ： 将 prev 添加到 prevMap[arr[i]][newLen] 中 如果 prev 不在 len 中： 初始化 len[arr[i]] = 1 初始化 prevMap[arr[i]][1] = [] （空列表，表示没有前驱，是第一个数） 步骤 4：回溯构造所有最长序列 遍历结束后，我们找到所有 len[x] == maxLen 的 x ，然后对每个 x 进行回溯。 回溯函数 backtrack(x, length, current_seq) ： 将 x 加入 current_seq 如果 length == 1 ，说明已经回溯到序列开头，将 current_seq 反转后加入结果集。 否则，遍历 prevMap[x][length] 中的每个前驱 prev ，递归调用 backtrack(prev, length-1, current_seq) 。 由于可能有多个前驱，会生成不同的序列。注意去重，因为不同路径可能产生相同序列。 步骤 5：复杂度分析 时间复杂度： 计算长度和个数：O(n)，n 是数组长度。 回溯构造序列：在最坏情况下，可能是指数级的（如果每个数字都有多个前驱），但实际中通常不会太大，因为数字范围有限。 空间复杂度：O(n) 存储 dp 和 prevMap。 示例演示 以示例数据详细走一遍步骤 3 和 4 的 prevMap 构造： arr = [1,5,7,8,5,3,4,2,1] , diff = -2 遍历： i=0, x=1: len[ 1]=1, prevMap[ 1][ 1]=[ ] i=1, x=5: len[ 5]=1, prevMap[ 5][ 1]=[ ] i=2, x=7: len[ 7]=1, prevMap[ 7][ 1]=[ ] i=3, x=8: len[ 8]=1, prevMap[ 8][ 1]=[ ] i=4, x=5: prev=7, len[ 7]=1 → newLen=2 > len[ 5]=1 → len[ 5]=2, prevMap[ 5][ 2]=[ 7 ] i=5, x=3: prev=5, len[ 5]=2 → newLen=3 > len[ 3]=0 → len[ 3]=3, prevMap[ 3][ 3]=[ 5 ] i=6, x=4: len[ 4]=1, prevMap[ 4][ 1]=[ ] i=7, x=2: prev=4, len[ 4]=1 → newLen=2 > len[ 2]=0 → len[ 2]=2, prevMap[ 2][ 2]=[ 4 ] i=8, x=1: prev=3, len[ 3]=3 → newLen=4 > len[ 1]=1 → len[ 1]=4, prevMap[ 1][ 4]=[ 3 ] 最终， maxLen=4 ，满足 len[x]==4 的只有 x=1 。 回溯： 从 x=1, length=4 开始： prevMap[ 1][ 4] = [ 3 ] 递归到 x=3, length=3: prevMap[ 3][ 3]=[ 5 ] 递归到 x=5, length=2: prevMap[ 5][ 2]=[ 7 ] 递归到 x=7, length=1: prevMap[ 7][ 1]=[]，回溯结束，序列为 [ 7,5,3,1 ]。 所以结果是： 最长长度 = 4 最长序列个数 = 1 最长序列列表 = [ [ 7,5,3,1] ] 总结 这个题目是 最长定差子序列 问题的进阶版，不仅要长度，还要统计个数和具体序列。 我们通过动态规划记录长度和前驱信息，然后通过回溯构造序列。 在实现时要注意去重，并合理使用哈希表存储中间结果，以避免指数级空间开销。 这个题目的难点在于 如何在动态规划过程中保存足够的信息以便后续构造所有序列 ，同时保证效率。