Previous post: Binary search done right: finding the median of a union in logarithmic time

<aside> 💡 Problem. Identify the length of the longest increasing subsequence of a given sequence.

</aside>

You can test your solutions with LeetCode problem #300. The difficulty “medium” corresponds to a quadratic DP solution, while the presented approach in $\mathcal O(n \log n)$ would be rather classified as “hard”, and it works for larger arrays within given time constraints.

This post is an adaptation of a translated post from e-maxx.ru, check out other algorithms there.

Longest increasing subsequence

cp-algorithms.com has lots of useful algorithms and data structures

Reminder. Python’s slicing operation $a[i:j]$ corresponds to a half-open interval $[i,j)$, which is equivalent to

[a[i], a[i+1], ..., a[j-1]]

Dynamic programming approach

A decent dynamic programming approach in $\mathcal O(n^2)$.

• Let $(a[i])_{i=0}^{n-1}$ be the initial array.
• Let $d[i]$ denote the length of the longest increasing subsequence of the array $a[0:i]$ ending in position $i$.

Then, we can recursively calculate the values $d[i]$ by trying all possible last positions and updating if necessary:

$$ d[i+1] = \max_{j\in[0,i) \colon a[j]<a[i]} d[j] + 1 $$

Conventionally, if the set is empty, we set its max to 0, because there would be no paths starting before the current position, and therefore, the maximal length of a sequence terminating at that point should be 1.

Finding the value of the next element requires scanning over $\mathcal O(n)$ elements, and therefore, the final complexity is quadratic.

This algorithm is easy to code, but there exists a faster algorithm which uses a mixture of binary search and dynamic programming.

Retrospective