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.

• 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? – Discrete lizard Jan 21 '18 at 16:11
• 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... – Raokfc Rdkf Jan 21 '18 at 19:51

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

• 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. – Daniel Saad Apr 15 '18 at 22:34
• 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). – Yuval Filmus Apr 16 '18 at 5:27

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.

• Yes you are right. I misunderstood the statement. – Daniel Saad Mar 9 '18 at 14:05