Longest Subsequence With Decreasing Adjacent Difference - Solution & Explanation

Problem 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.