Content deleted Content added
m whitespace |
|||
Line 8:
The longest increasing subsequence problem can also be related to finding the [[longest path problem|longest path]] in a [[directed acyclic graph]] derived from the input sequence: we construct a vertex per sequence value and connect values ''x'' and ''y'' by an edge when ''x'' is both smaller than ''y'' and occurs earlier than it in the sequence. Longest paths in DAGs can be found in time linear in the size of the DAG, but in this case the size can be quadratic in the sequence length, so this algorithm is not asymptotically faster than the dynamic programming one.
== Efficient algorithms ==
| |||