Longest Subsequence With Decreasing Adjacent Difference
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
3The longest subsequence is
[16, 6, 3] with the absolute adjacent differences [10, 3].Example 2
Input
nums = [6,5,3,4,2,1]Output
4The longest subsequence is
[6, 4, 2, 1] with the absolute adjacent differences [2, 2, 1].Constraints
- 2 <= nums.length <= 10^4
- 1 <= nums[i] <= 300
Asked at 2 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.