<p>There is a $O(n \log \log n)$ time algorithm to solve the longest increasing subsequence problem. You may find <a href="https://en.wikipedia.org/wiki/Patience_sorting#cite_note-Bespamyatnikh-3" rel="nofollow noreferrer">this</a> and the paper by <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.5912" rel="nofollow noreferrer">Sergei Bespamyatnikh , Michael Segal</a> helpful.</p>

CC BY-SA 3.0
2017-08-21T05:16:55.257Z
2017-08-21T05:16:55.257Z
Dibyayan
<p>The <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence" rel="nofollow noreferrer">longest increasing subsequence</a> problem has a simple and elegant $O(n \log n)$ time solution via patience sorting.</p>

<p>Such a basic and well-studied problem, however, should have a number of different solutions, just as sorting does.</p>

<p>Are there other distinct $O(n \log n)$ time algorithms for this problem?</p>

<ds.algorithms><reference-request>
Different algorithms for longest increasing subsequence
Simd
# Different algorithms for longest increasing subsequence

(Asked by: username_0 on 2017-08-20)

The [longest increasing subsequence](https://en.wikipedia.org/wiki/Longest_increasing_subsequence) problem has a simple and elegant $O(n \log n)$ time solution via patience sorting.

Such a basic and well-studied problem, however, should have a number of different solutions, just as sorting does.

Are there other distinct $O(n \log n)$ time algorithms for this problem?

**Tags:** ds.algorithms, reference-request


---

## 1 answers

### Answer by username_1 on 2017-08-21. Score: 3

There is a $O(n \log \log n)$ time algorithm to solve the longest increasing subsequence problem. You may find [this](https://en.wikipedia.org/wiki/Patience_sorting#cite_note-Bespamyatnikh-3) and the paper by [Sergei Bespamyatnikh , Michael Segal](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.5912) helpful.


---

