Find longest subsequence in array with given condition

I am given an array $A$ having $n$ elements and an integer $k$.

I need to find the longest subsequence which always includes the first element and the subsequence follows the given condition:

for all $i < j$: $|A[i] - A[j]| \leq k$.

Example: $n= 4$, $k = 5$, $A = [1, 2, 50, 6]$

Answer: the longest valid subsequence, $[1, 2, 6]$, has length $3$.

Note that the first element is always to be included in the sequence.

I think this can be solved with Dynamic Programming. But I can't form a recursive equation for Dynamic Programming.

In the following answer, I show how to solve in $O(n\log n)$ the following similar question:


Given an array $A$ and a number $k$, find the longest contiguous subsequence in which any two elements $x,y$ satisfy $|x-y| \leq k$.

Using this, it is easy to solve in $O(n \log n)$ the following question, closer to yours:


Given an array $A$ and a number $k$, find the longest subsequence in which any two elements $x,y$ satisfy $|x-y| \leq k$.

Indeed, sort $A$ and then find the longest contiguous subsequence satisfying the condition.

Finally, to solve your actual question, filter $A$ by removing all elements at distance more than $k$ from the first element. The longest subsequence is now guaranteed to contain the first element (since it can always be added), so we can run the preceding algorithm to solve your question in $O(n\log n)$.

StackExchange Computer Science Q#87082, answer score: 4