Longest Increasing Subsequence using dynamic programming explained

Another day, another DP problem. Earlier I wrote a tutorial explaining the intuition of DP using the infamous coin change problem. I suggest you read it here before proceeding.

Another popular DP problem asked in interviews is the Longest Increasing Subsequence (LIS) problem. Let’s take an example question and learn this.

Qn. Given an unsorted array of integers determine the length of the longest subsequence whose elements are in strictly ascending order.

Input: [2, 4, 3, 7, 4, 5] → Arr

Output: 4 ( [2, 3, 4, 5] → LIS )

Brute Force

The naive solution is to consider all non-null subsets of Arr. Then collect all the increasing subsequences and return the longest subsequence from them. This is O(2^n) since the number of subsets of a set of size n in 2^n. Doesn’t sound all that elegant right.

O(n²) with DP

This is my favourite solution as it is very intuitive to understand. Initially, LIS is empty. As a base case, we assume a single element list is a LIS, although there’s nothing increasing about it. Now, we start from the left and look at each element.

ref. [2, 4, 3, 7, 4, 5] → Arr

1. 2 by itself is a LIS. (base case)
2. 4 by itself is also a LIS, but along with 2, it forms a longer LIS.
3. Similarly, 3 by itself is also a LIS, but along with 2, it forms a longer LIS. It can’t form an Increasing Subsequence with 4.
4. 7 forms a LIS with either [2, 3] or [2, 4]
5. 4 forms LIS with [2, 3]
6. 5 forms LIS with [2, 3, 4, 5]

Various LIS candidates. The final LIS is highlighted in green.

Take a look at the figure above. You can observe every element appends itself to the longest LIS previously formed (or starts a LIS by itself as a base case if there is none longer before, here, it’s the starting element 2).

# len_of_lis[i] -> length of Longest Incresing Subsequence of all
# elements upto Arr[i]
len_of_lis[i] = max(len_of_lis[j] + 1) # where j<i and Arr[j]<Arr[i]

How is this O(n²)?

We traverse through the array O(n), and for each element i we find a j through linear search O(n). Effectively O(n²).

O(nlogn) with DP

This idea is not very intuitive (to me at least), so you have to put up with a “just makes sense” explanation. Readers are welcome to comment explanations of their own.

From the n² solution, you can observe that at any instant there are more than one candidates for LIS. Here, we have an array end_elements where end_elements[i] holds the last element of the LIS of length i. Initialise end_elements with NULL for all i. After we are done, the largest i for which end_elements[i] is not NULL will be the length of LIS.

Here too, we start from the left and look at each element of Arr and update end_elements as we go. There are 3 rules to update end_elements :

1. if Arr[i] is the smallest element seen yet end_elements[1] = Arr[i]
2. if Arr[i] is the largest element seen yet extend end_elements with Arr[i]
3. If Arr[i] is somewhere in the middle, find k such that end_elements[k] is the least number greater than Arr[i] and replace end_elements[k] with Arr[i].

Why do these rules work?

1. The smallest element can NOT be part of any previous candidate LIS and has to start a LIS on its own. Consider [3,1,2,4,5] : Initially you have end_elements[1] = 3. Then end_elements[1] becomes 1. This is because 1 has a better potential of creating a new LIS than 3, as in this case [1,2,4,5] instead of [3,4,5].
2. Since we want the Longest Increasing Subsequence we use the largest element to extend the best candidate LIS. It doesn’t make sense to do anything else with the largest number seen yet.
3. Consider [1,4,2,3]. At i = 2, Arr[i] = 2, Active LIS : [1], [1, 4]. The rule says drop [1,4] in favour of [1,2]. We do this because [1,2] and [1,4] despite being equal in length [1,2] has more potential to form a better LIS than [1,4] as in this case it forms [1,2,3].

Ideally we would like to keep track of all candidate LIS and update them as we see new elements, but apparently, we can get away with tracking just last elements of all candidate LIS.

ref. [2, 4, 3, 7, 4, 5] → Arr

1. 2 is the first element. So end_elements[1] = 2 . Active LIS : [2]
2. 4 > 2. end_elements[2] = 4 . Active LIS : [2], [2, 4]
3. 3 < 4. end_elements[2] = 3 . Active LIS : [2], [2, 3]
4. 7 > 3. end_elements[3] = 7 . Active LIS : [2], [2, 3], [2, 3, 7]
5. 4 < 7. end_elements[3] = 4 . Active LIS : [2], [2, 3], [2, 3, 4]
6. 5 > 4. end_elements[4] = 5 . Active LIS : [2], [2, 3], [2, 3, 4], [2, 3, 4, 5]

Thus the length of LIS is 4.

How is this O(nlogn)?

We traverse through Arr once O(n) and for each element, we go through the rules. the first and second rule is O(1) but the third is O(n). So we are again at O(n²). The trick here is that these 3 rules ensure that end_elements is always sorted (Check for yourselves). So we leverage binary search bringing the net complexity to O(nlogn).

The code for both the DP solutions is given below. Feedback/suggestions are welcome. Thanks for reading.