Find longest subsequence in array with given condition

Question

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.

• Discrete lizard: What did you try to construct the recurrence equation? In particular, what subproblem for to the recursion did you consider? Would $C[i] = $ 'the length of the largest valid subsequence in $A[1..i]$' work? If not, why?
• Raokfc Rdkf: Recurrence Relation: for i = 1 to n: for j = 1 to i: if(abs(a[j]-a[i])<=k) dp[j] = max(dp[j], dp[i]+1) But this didn't work...

Answer 1

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)$.

• Daniel Saad: Hi Yuval. Please, correct if I'm wrong. But I'm afraid that If you sort you do not preserve the original order, and hence, you can't talk about subsequences anymore.
• Yuval Filmus: You can keep track of the permutation if you wish. This isn't necessary if you're only interested in the elements comprising the longest subsequence (rather than their order).

Answer 2

The solution by Daniel Saad is on the right track, but unfortunately isn't complete. It's not difficult to come up with an example when the greedy algorithm fails and hence the item should be better excluded even if it satisfies the condition when it's processed:

Let $A=(1, 0, 2, 2)$ and $k=1$. The answer is $(1, 2, 2)$ and one would make a mistake by including 0ドル$ into a subsequence, because it will shut the door for both 2ドル$s. Obviously, the skip sequence can be arbitrarily long, e.g. $A=(1, 0, ..., 0, 2, 2, ..., 2)$.

Moreover, an algorithm that tries to complete any previous subsequence is also wrong, because the principle of optimality isn't satisfied. Consider this example:

Let $A=(0, 1, -1, 0, 2, 2, 2, 2)$ and $k=2$. The optimal sequence up to $A[4]$ is $(0, 1, -1, 0)$ (contains all items). But the answer up to $A[5]$ is not completing the best sequences up to $A[4]$ or up to $A[2]$! The best subsequence actually includes $A[4]=0$ and excludes $A[3]=-1$.

---

The algorithm I came up fills the table $T[i, p, q],ドル which designates the best subsequence that ends with item $i,ドル the minimum of which is $A[p]$ and the maximum is $A[q]$ ($p \leq i$ and $q \leq i$). This means that on each step $i,ドル the list of candidates is going to hold up to $i^2$ values, for each $(A[p], A[q])$ pair from $A[1..i]$. The total time is $O(n^4)$!

The base equation is trivial. The transition on step $i+1$ computes the list of candidates by completing all candidates from the previous steps $T[j],ドル $j \leq i$. The total number of candidates is $O(n^3)$. I leave you the task of writing formal recursive equations as an exercise.

• Daniel Saad: Yes you are right. I misunderstood the statement.