求相邻元素差绝对值≤1的最长非连续子序列长度解法求助

这个问题属于典型的动态规划适用场景，我们可以通过两种方案实现：

基础动态规划方案（时间复杂度O(n²)） #

• 定义dp[i]表示以数组第i个元素作为结尾的符合条件的最长子序列长度
• 初始状态：每个dp[i]默认值为1，因为单个元素本身就是长度为1的合法子序列
• 转移方程：对每个位置i，遍历它前面所有的位置j（j < i），如果满足abs(arr[i] - arr[j]) ≤ 1，那么dp[i] = max(dp[i], dp[j] + 1)
• 最终结果就是整个dp数组中的最大值
  这个方案逻辑直观好理解，适合数组长度不大的场景（长度≤1e3都可以正常运行）。

优化动态规划方案（时间复杂度O(n)，仅适用于元素数值范围不大的场景） #

如果数组元素的数值范围很小，我们可以进一步优化复杂度：

• 定义max_len[v]表示所有以数值v结尾的合法子序列的最大长度
• 遍历数组中每个元素x：
  • 当前元素能接上的最长子序列长度为 max(max_len[x-1], max_len[x], max_len[x+1]) + 1
  • 如果上述计算结果比max_len[x]原有值更大，就更新max_len[x]
• 遍历过程中记录的全局最大值就是最终结果
  这个方案只需要一次遍历就能得到结果，效率极高。

我们用你给出的测试用例验证优化方案的正确性：

测试用例1：输入[4,6,5,3,3,1]
遍历过程：
4：max(max_len[3],max_len[4],max_len[5])+1 = 0+1=1 → max_len[4]=1，全局最大值1
6：max(max_len[5],max_len[6],max_len[7])+1=1 → max_len[6]=1，全局最大值1
5：max(max_len[4],max_len[5],max_len[6])+1 = max(1,0,1)+1=2 → max_len[5]=2，全局最大值2
3：max(max_len[2],max_len[3],max_len[4])+1 = max(0,0,1)+1=2 → max_len[3]=2，全局最大值2
3：max(max_len[2],max_len[3],max_len[4])+1 = max(0,2,1)+1=3 → max_len[3]=3，全局最大值3
1：max(max_len[0],max_len[1],max_len[2])+1=1 → 全局最大值保持3
最终输出3，和预期一致。

测试用例2：输入[4,6,5,3,2,1]
遍历到2的时候，max(max_len[1],max_len[2],max_len[3])+1 = max(0,0,2)+1=3；遍历到1的时候，max(max_len[0],max_len[1],max_len[2])+1 = max(0,0,3)+1=4，最终输出4，符合预期。

测试用例3：输入[1,2,2,3,4,5]
每一步都可以接上前一个数值的最长子序列，最终得到最大值6，符合预期。

# 优化版实现
def max_subsequence_length(arr):
    max_len = dict()
    res = 0
    for x in arr:
        current = max(
            max_len.get(x-1, 0),
            max_len.get(x, 0),
            max_len.get(x+1, 0)
        ) + 1
        if current > max_len.get(x, 0):
            max_len[x] = current
        if current > res:
            res = current
    return res

内容的提问来源于stack exchange，提问作者Rigelel