# Longest subsequence such that A[i].x < A[i+1].y

I have an issue for which I am looking for an algorithm (if it exists)

What I have: An array of items which have certain properties, e.g. item $A$ has properties $x$ and $y$.

Example: $[ A(x,y), B(x,y), C(x,y), D(x,y), E(x,y) ]$

What I want: A result list consisting of elements of the original list, such as $[ A(x,y), C(x,y), E(x,y) ]$, for which the following properties are true:

• No reordering of elements, they are in the same order as the original list
• The result has the maximum number of elements, i.e. the longest 'path' possible
• For each pair of consecutive items $(A(x,y), B(x,y))$ in the result, $A.x \lt B.y$. In other words, an item's $x$ must be less than the next item's $y$.

Complexity: The list in the case I have is about 35 items long, so an algorithm which is $O(n!)$ might not work.

Does such an algorithm exist?

• Perhaps try a backtracking algorithm? That should be O(2^n) which you could always change to a dynamic program of (hopefully) O(n^2). The only problem I forsee is that the recursion has no idea if you choose to include A not C, whether or not A.x < E.y. – ardent Jun 19 '13 at 19:41
• – András Salamon Jun 19 '13 at 21:28
• @AndrásSalamon Yes, that looks very much related – Dutchy Jun 20 '13 at 9:25
• @AndrásSalamon $A.x < B.y$ isn't transitive, I think this makes a big difference. – Gilles 'SO- stop being evil' Jun 20 '13 at 9:49

It's easier to change notation. Suppose the array is $A$, with the $i$-th element denoted $A[i]$ for $i=1,2,\dots,n$, and that element $i$ has attributes $A[i].x$ and $A[i].y$. Associate a directed graph $G$ with the array as follows. The vertices of $G$ are the indices $1\dots n$ of the array. Vertex $i$ is connected to vertex $j\$ if both conditions $i<j$ and $A[i].x < A[j].y\$ hold.
You are then asking for a longest directed path in $G$.
Note that $G$ is actually acyclic, since the arcs form a subset of the usual order on the set $\{1,\dots,n\}$. Any standard linear algorithm can then be used to compute the longest path, such as a topological sort.