Technical Interviews: Longest Increasing Subsequence

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[0]]
    current = [_list[0]]
    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.