Longest Subsequence With Decreasing Adjacent Difference

Longest Subsequence With Decreasing Adjacent Difference

What is this problem about?

In this problem, you are given an array of integers. You need to find the length of the longest subsequence such that the absolute difference between adjacent elements in the subsequence is strictly decreasing (or non-increasing, depending on the exact variant). For example, if differences are 5, then 3, then 1, the condition holds.

Why is this asked in interviews?

This question is a deep test of Dynamic Programming. Interviewers ask it to evaluate if a candidate can track multiple states simultaneously. Unlike standard LIS (Longest Increasing Subsequence) where you only care about the previous value, here you must track BOTH the previous value AND the previous difference. It highlights a candidate's ability to model complex 2D DP states effectively.

Algorithmic pattern used

This problem relies on a 2D Dynamic Programming pattern. We define dp[i][diff] as the maximum length of a valid subsequence ending at index i with an absolute difference of exactly diff between nums[i] and the element before it. To calculate this, we iterate through previous indices j, calculate current_diff = abs(nums[i] - nums[j]), and then look for the maximum dp[j][prev_diff] where prev_diff >= current_diff.

Example explanation

Assume nums = [10, 5, 8, 7].

• Pair (10, 5): Diff is 5. Sequence is [10, 5]. Length = 2. dp[5_idx][5] = 2.
• Pair (5, 8): Diff is 3. We check sequences ending at 5 with diff $\ge 3$. The sequence [10, 5] had a diff of 5. Since $5 \ge 3$, we can append 8! Sequence becomes [10, 5, 8]. Length = 3.
• Pair (8, 7): Diff is 1. We check sequences ending at 8 with diff $\ge 1$. The sequence [10, 5, 8] had a diff of 3. Since $3 \ge 1$, we can append 7! Sequence becomes [10, 5, 8, 7]. Length = 4. The longest sequence is 4.

Common mistakes candidates make

The most frequent mistake is using a simple 1D DP array, which simply doesn't hold enough information. You cannot determine if you are allowed to append a number without knowing the last gap established. Another mistake is using nested loops that iterate through all previous differences, resulting in $O(N^2 \times \text{MaxDiff})$ time, which can trigger Time Limit Exceeded if not optimized by keeping track of running maximums.

Interview preparation tip

For this interview pattern, get very comfortable with dictionary-based DP or 2D DP arrays where the second dimension represents a "constraint" or a "score" (like the difference). When the transition of a DP state depends on a property of the edge connecting two elements rather than just the elements themselves, a 2D state is mandatory.