An efficient parallel solution for the longest increasing subsequence problem
Christophe Cérin, Catherine Dufourd, Jean‐Frédéric Myoupo · 2002
We derive a parallel solution to the problem of finding the longest increasing subsequence in a finite sequence of numbers. We first describe a sequential solution with time complexity O(n log n) and space complexity O(n). Secondly, we show how a parallel solution can be obtained using a partially pipelined linear modular systolic array, with time complexity O(n).>