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?