Daily bit(e) of C++ | Longest increasing subsequence
Daily bit(e) of C++ #261, Common interview problem: Longest increasing subsequence.
Today, we will look at a common C++ interview problem: Longest increasing subsequence.
Given an array of integers (std::vector<int>), determine the length of the longest increasing (not necessarily contiguous) subsequence.
For example, for the input {2,8,3,6,4,5}, the longest subsequence is {2,3,4,5} of length four.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/r3x953ajK.
Solution
A reasonably straightforward approach with O(n^2) complexity is a dynamic programming approach.
Let’s consider the maximum subsequence ending in a particular element. We can calculate the length by iterating over all maximum subsequences that end in preceding elements with strictly lower values.
With this logic, we can then build the solution bottom up.
However, we can also solve this problem in O(nlogn) time.
Let’s consider building the maximum subsequence iteratively. The simplest case is when we consider a value higher than the end of the subsequence; then, we can extend the subsequence with it: {2} → {2,8}.
The second observation is less straightforward. When we encounter a value equal to or less than the current end of the subsequence, we can insert it into the candidate subsequence by overwriting the next higher element.
For example, for the input {2,8,3,6,4,5}:
increasing: {}→{2}→{2,8}
replace: {2,8}→{2,3}
increasing: {2,3}→{2,3,6}
replace: {2,3,6}→{2,3,4}
increasing: {2,3,4}→{2,3,4,5}
Note that we are not necessarily building a correct maximum subsequence; however, the length property is maintained. Example: {2,3,4,1}, results in {1,3,4}.
The main reason why this approach works is because it is monotonic. We only decrease the values in our candidate subsequence, so we never break any subsequences we have already iterated over, and we also cannot accidentally shorten the subsequence by overwriting the value. The first rule ensures that we extend the subsequence whenever possible, guaranteeing that we find the maximum length.
