3409. 最长相邻绝对差递减子序列
题目描述
给你一个整数数组 nums 。
你的任务是找到 nums 中的 最长 子序列 seq ，这个子序列中相邻元素的 绝对差 构成一个 非递增 整数序列。换句话说，nums 中的序列 seq0, seq1, seq2, ..., seqm 满足 |seq1 - seq0| >= |seq2 - seq1| >= ... >= |seqm - seqm - 1| 。
请你返回这个子序列的长度。
示例 1：
输入：nums = [16,6,3]
输出：3
解释：
最长子序列是 [16, 6, 3] ，相邻绝对差值为 [10, 3] 。
示例 2：
输入：nums = [6,5,3,4,2,1]
输出：4
解释：
最长子序列是 [6, 4, 2, 1] ，相邻绝对差值为 [2, 2, 1] 。
示例 3：
输入：nums = [10,20,10,19,10,20]
输出：5
解释：
最长子序列是 [10, 20, 10, 19, 10] ，相邻绝对差值为 [10, 10, 9, 9] 。
提示：
2 <= nums.length <= 1041 <= nums[i] <= 300
解法
方法一
思考
子序列要求相邻差的绝对值严格递减。\(n\le 10^4\)，若按子序列子集枚举不可行；值域却只有 \([1,300]\)，相邻差至多 \(299\)。
决策只依赖于「当前结尾的值」与「上一段相邻差」，据此转移可以在值域上完成。
设 \(f[v][d]\) 为以值 \(v\) 结尾、最后一段差为 \(d\) 的最长长度。加入 \(x\) 时枚举上一个值 \(y\) 与差 \(d>|x-y|\)，用 \(f[y][d]\) 更新 \(f[x][|x-y|]\)。值域有限，总时间可接受。
1 | |
1 | |
1 | |
1 | |