Grokking Dynamic Programming Interview/

...

/

Longest Increasing Subsequence

Longest Increasing Subsequence

Let's solve the Longest Increasing Subsequence problem using Dynamic Programming.

We'll cover the following...

Statement

The Longest Increasing Subsequence (LIS) is the longest subsequence from a given array in which the subsequence elements are sorted in strictly increasing order. Given an integer array, nums, find the length of the LIS in this array.

Let’s say we have an integer array [6, 9, 8, 2, 3, 5, 1, 4, 7], and we want to get the longest increasing subsequence in this array. There are multiple increasing subsequences of different lengths, such as [6, 9], [6, 8], [2, 3, 5], [2, 3, 5, 7], and so on. The longest increasing subsequences, in this case, are [2, 3, 4, 7] and [2, 3, 5, 7], both of length 4.

Constraints:

  • 1≤1 \leq nums.length ≤6000\leq 6000
  • −109≤-10^9 \leq nums[i] ≤109\leq 10^9

Examples

No.

Input

Output

LIS Elements

1

[6, 9, 8, 2, 3, 5, 1, 4, 7]

4

[2, 3, 5, 7]

2

[1, 3, 6, 7, 9, 4, 10, 5, 6]

6

[1, 3, 6, 7, 9, 10]

3

[5, 5, 5, 5, 5, 5, 5]

1

[5]

Try it yourself

Implement your solution in the following playground.

Press + to interact
Java
usercode > LIS.java
import java.util.*;
class LIS {
    public static int lisLength(int[] nums) {
        // write your code here
        return -1;
    }
}
Longest Increasing Subsequence

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach

Let’s first list down all the ideas that are needed to find the solution to this problem:

  • Each element of the array is either a part of an increasing subsequence or it is not.
  • To be part of an increasing subsequence, the current element needs to be greater than the previous element included in the subsequence.
  • To find the longest increasing subsequence, we need to move from left to right, exhaustively generating all increasing subsequences, while keeping track of the longest one found at any step.

Now, let’s consider how we might write a recursive solution to this problem. The first thing to figure out is the base case: we’re moving from the start of the array to the end and we need to consider all the elements. We may skip ...

Access this course and 1400+ top-rated courses and projects.