One of the questions you may be asked in a technical interview is to find the longest increasing subsequence of a list of numbers. There are multiple approaches to this problem. What’s your instinct? Let’s take a look at the most efficient way to get the longest increasing subsequence in Python.
The common approach from beginners is to do a nested for loop, checking for the longest increasing subsequence starting from each number. In this post we’re going to cover the best way to solve this problem in Python. The best way to approach this problem gives you a linear time complexity and a constant space complexity.
In this post we’ll go through:
- Setting up some examples for solving longest possible subsequence with Python
- Longest Increasing Subsequence Python Algorithm
- Longest Increasing Subsequence Python Algorithm Output
Setting Up Some Examples
Here’s some examples with the right answers in comments next to them that we will test our algorithm on. Note that example
t6 may have a different answer depending on if the problem is asking for a longest monotonically increasing subsequence or a longest strictly increasing subsequence. Monotonically increasing just means the numbers in the subsequence don’t decrease, they can stay even. Otherwise, example 6 would only have one 6 in the front.
# for a list of numbers find the longest increasing subsequence t1 = [0, 4, 3, 2, 6, 7, 9] # 2, 6, 7, 9 t2 = [0, 1, 3, 2] # 0, 1, 3 t3 = [8, 5, 4, 1] # 8 t4 = [3, 5, 2, 7, 9, 10, 1] # 2, 7, 9, 10 t5 = [6, 5, 3, 1, 8] # 1, 8 t6 = [6, 6, 9, 10, 11, 0] # 6, 6, 9, 10, 11
Longest Increasing Subsequence Python Algorithm
Let’s start by creating a function called
lis (for “longest increasing subsequence”). It will take one parameter, a list. To start off, our function will create two lists both consisting of the first element of the passed in list. The first list we create will keep track of the longest subsequence so far, and the second one we create will keep track of the length of the current subsequence we’re on. Note that by starting these lists off as the first element of the passed in list, we’re assuming that we won’t encounter any empty lists in our test cases.
Now we loop through every element after the first. If the element is greater than or equal to the last element of the current subsequence, we’ll append the element to the current subsequence. Otherwise, if the current subsequence is longer than the longest subsequence, we’ll replace the longest increasing subsequence and start a new subsequence consisting of just the element we’re on.
Comparing to the
[-1]th element is a nice syntactical sugar only available in Python as far as I know. If we’re looking for a strictly increasing subsequence, we simply change the greater than or equal to sign to just a greater than sign. After we’ve looped through the whole list, if the current subsequence we’re processing is greater than the longest subsequence list, we’ll replace the longest subsequence list with our current one. Finally, we return the longest subsequence list.
def lis(_list): longest = [_list] current = [_list] for i in _list[1:]: if i >= current[-1]: current.append(i) else: if len(longest) < len(current): longest = current current = [i] if len(longest) < len(current): longest = current return longest
The Longest Increasing Subsequence Python Algorithm Results
At the end, we can test our algorithm on our 6 lists and see the results.
print(lis(t1)) print(lis(t2)) print(lis(t3)) print(lis(t4)) print(lis(t5)) print(lis(t6))
As you can see, the results match up with the expected results exactly.
I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.
Make a one-time donation
Make a monthly donation
Make a yearly donation
Choose an amount
Or enter a custom amount
Your contribution is appreciated.
Your contribution is appreciated.
Your contribution is appreciated.DonateDonate monthlyDonate yearly