3409. Longest Subsequence With Decreasing Adjacent Difference
Description
You are given an array of integers nums.
Your task is to find the length of the longest subsequence seq of nums, such that the absolute differences between consecutive elements form a non-increasing sequence of integers. In other words, for a subsequence seq0, seq1, seq2, ..., seqm of nums, |seq1 - seq0| >= |seq2 - seq1| >= ... >= |seqm - seqm - 1|.
Return the length of such a subsequence.
Example 1:
Input: nums = [16,6,3]
Output: 3
Explanation:
The longest subsequence is [16, 6, 3] with the absolute adjacent differences [10, 3].
Example 2:
Input: nums = [6,5,3,4,2,1]
Output: 4
Explanation:
The longest subsequence is [6, 4, 2, 1] with the absolute adjacent differences [2, 2, 1].
Example 3:
Input: nums = [10,20,10,19,10,20]
Output: 5
Explanation:
The longest subsequence is [10, 20, 10, 19, 10] with the absolute adjacent differences [10, 10, 9, 9].
Constraints:
2 <= nums.length <= 1041 <= nums[i] <= 300
Solutions
Solution 1
Thinking
Adjacent absolute differences in the subsequence must strictly decrease. \(n\le 10^4\) rules out subset enumeration, but values lie in \([1,300]\), so differences are at most \(299\).
A state only needs the last value and the last difference; transitions can run over that small domain.
Let \(f[v][d]\) be the longest subsequence ending with value \(v\) whose last difference is \(d\). When inserting \(x\), we enumerate a previous value \(y\) and a larger difference \(d>|x-y|\), and update \(f[x][|x-y|]\) from \(f[y][d]\).
1 | |
1 | |
1 | |
1 | |