Search⌘ K
AI Features
Home
Courses
Grokking Dynamic Programming Interview in Python

Longest Increasing Subsequence

Explore how to identify and implement the longest increasing subsequence in an integer array using both naive recursive and optimized dynamic programming approaches. Understand the recursive case reasoning, subproblem structure, and efficient top-down and bottom-up solutions, including space optimization. Gain skills to apply these methods in coding interviews effectively.

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 ≤985\leq 985
  • −104≤-10^4 \leq nums[i] ≤104\leq 10^4

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.

Python
usercode > main.py
def LIS_length(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: ...