Watch 4 video solutions for Longest Subsequence With Decreasing Adjacent Difference, a medium level problem involving Array, Dynamic Programming. This walkthrough by Aryan Mittal has 5,438 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 300Problem Overview: Given an integer array, find the longest subsequence where the absolute difference between consecutive elements never increases. If the previous difference is d1 and the next is d2, the rule is d1 >= d2. The subsequence does not need to be contiguous, but order must remain the same.
Approach 1: Brute Force Subsequence Enumeration (Exponential Time, O(2^n) time, O(n) space)
Generate every possible subsequence and check whether its adjacent absolute differences form a non‑increasing sequence. For each candidate subsequence, iterate through its elements and verify the difference constraint. This approach demonstrates the problem definition clearly but quickly becomes impractical because the number of subsequences grows exponentially with n. Useful only for reasoning or validating small examples.
Approach 2: Dynamic Programming with Previous Difference Tracking (O(n^3) time, O(n^2) space)
Define a DP state that tracks the subsequence ending at index i with the last adjacent difference d. For each pair (j, i) where j < i, compute diff = |nums[i] - nums[j]|. Extend any subsequence ending at j whose last difference is greater than or equal to diff. This requires scanning all possible previous differences at j, which leads to an extra loop. The approach correctly models the constraint but is too slow for large inputs.
Approach 3: Optimized Dynamic Programming with Difference States (O(n^2 + n·D) time, O(n·D) space)
Store dp[i][d] as the longest valid subsequence ending at index i with last difference exactly d. When processing a pair (j, i), compute diff = |nums[i] - nums[j]|. Instead of scanning all larger differences, maintain suffix maximums so you can query the best subsequence at j with previous difference ≥ diff in constant time. Update dp[i][diff] with that value plus one. Because the difference range D is bounded by the value range of the array, this reduces the complexity close to O(n^2). This technique combines ideas from dynamic programming and difference-based state compression over an array.
Recommended for interviews: The optimized dynamic programming approach. Interviewers expect you to model the constraint using a DP state that tracks the last difference, then eliminate the inner scan using prefix or suffix maximums. Mentioning the brute force and the naive DP shows you understand the progression from exponential search to efficient state transitions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subsequence Enumeration | O(2^n) | O(n) | Conceptual understanding or verifying very small inputs |
| DP with Previous Difference Scan | O(n^3) | O(n^2) | Shows the correct DP state but not optimized |
| Optimized DP with Difference States | O(n^2 + n·D) | O(n·D) | General solution expected in interviews and competitive programming |