Leetcode 300: Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7]

Example:

Input: nums = [2, 1, 0, 3, 2, 3]
Output: 3
Explanation: The longest increasing subsequence is [1, 2, 3], therefore the length is 3
Note that there can be multiple longest increasing subsequences of same length

This is a good problem to practice recursion and Dynamic Programming. I will show how to code the solution in Go using both approaches.

Method 1: Recursion — Brute Force Approach

When faced with a complex problem, coming up with a brute force solution is a good starting point. Such an approach helps in developing a clear understanding of the problem. Once the brute force solution is coded without errors, one can think about what kind of patterns the solution exposes and accordingly suggest optimum solutions.

To solve it using brute force method, I can express the original problem in terms of a slightly different problem. What if I can find the length of longest increasing subsequence that starts at a particular index? I can use that information to reformulate the original problem as —

Find the length of LIS that starts at each index and process these results to arrive at the required solution for the original problem.

The following picture shows LIS that starts at each position in the input array and the corresponding lengths.

Once we have the LIS lengths information corresponding to each index, we can process them to find the final result which in this case is finding the maximum out of all those LIS lengths. The following code snippets shows this.

Now, the question becomes how to find out length of LIS that starts from a particular index. This can be trivially coded using recursion. When working with recursion, one has to carefully consider the base cases that will break the recursion. That is, the solution for base case(s) is trivial and it must be coded. The base case in this case is finding the LIS length of a sequence that starts at last index of the input. This value is simply 1 which can be returned without recursion.

That’s it. Connecting those two code snippets in your program should work. However this solution is going to be terribly slow. The reason for this is we are solving the same subproblems again and again i.e. we are repeating the same work. The solution can be improved by using a programming paradigm called Dynamic Programming (DP). Solving problems using DP technique is quite satisfying and it’s not difficult if we follow a systematic approach. In general, there are two approaches within DP which you will frequently come across. These are —

• Top-down approach — this technique caches intermediate results to avoid re-computing
• Bottom-up approach — this technique builds the final solution in a bottom-up fashion (i.e. solves subproblems of smaller size first and uses those results to compute the solutions for bigger subproblems)

Before seeing the DP solution for this problem, let us look at Method 2 which is also a brute force approach but solves it little differently.

Method 2 Recursion — Brute Force Approach

In Method 1, we expressed the original problem in terms of the following:

Find the length of LIS that starts at each index and process these results to arrive at the required solution

However, we can also express it in terms of the following:

Find the lengths of LIS that ends at each index and process these results to arrive at the required solution

The following picture shows the details of the LIS ending at each position in the input and the corresponding lengths.

With that, we can easily code the top level function as shown below.

And writing the functions that computes length of LIS ending at a particular index is also very similar to Method 1. The base case here is to check if the end index is 0 and break out of recursion. The code for it is shown in the gist below.

This version of the program is no different in speed compared to Method 1. The reason I have included this is to show how to take this idea to Go code. Also, I improve this solution in Method 3 by using Dynamic Programming.

Method 3 Dynamic Programming Bottom-up Solution

As I mentioned earlier, DP comes in two flavors — top-down approach and bottom-up approach. I will show how to solve it using bottom-up technique here. The idea in bottom-up approach is simple. We solve the problem for smaller instances first and use those results for solving bigger subproblems. We use a table to store the results of the subproblems.

The first step is to create a table (i.e. an array) and initialize it with subproblems that are trivial to solve. The following code snippet just does that.

The next step is to compute the LIS length for all subproblems of increasing size.

To compute each dp[i], I will use previously computed results of the smaller subproblems. These values are available in the table from dp[0 to i-1].

To see how this can be done, let us assume that I have already computed the. LIS ending at indices 0, 1, 2, 3, 4 and I need to compute the LIS ending at index 5. The following picture shows the details.

As you can see, the inner loop in the code is where previously computed results are used in finding the solution for current subproblem marked by the index i.

Thanks for reading. I hope you enjoyed this article.