How to Get Longest Increasing Subsequence in Python

We will learn what a subsequence is and how to calculate the longest increasing subsequence from an array using the n-squared approach and the binary search approach in Python.

Use N-Squared Approach to Calculate the Longest Increasing Subsequence in Python

A famous question is asked about the longest-increasing subsequence around the Python community and asked in different interviews. It is a Leetcode problem, and the question says: an unsorted array of integers is given and find the length of the longest increasing subsequence or subset of the given array.

A subset is like a short array of an array; each array could have multiple subsets. The other thing is subarray would be some of the elements from this [10,9,2,5,3,7,101,18] array but in a continuous subsequence manner.

It can be like [2, 3, 5, 7], but it cannot be [2,3,101], so the sequence does not need to be broken when discussing a subarray. And, in subsequence, the order in which the elements appear in the array has to be the same, but it could be any of the individuals.

For example, in this case, as we can see, the answer is [2, 3, 7,101]; the 5 is not there, but that is ok because it is a subsequence.

If we see the longest increasing subsequence from [10,9,2,5,3,7,101,18], we find [2, 5, 7, 101]; this could also have meant an answer, but the answer also could be [2, 3, 7, 101] that is our other subsequence as well. The [3, 7, 101] is also a subsequence, but that is not the longest, so we will not consider it.

There may be more than one combination; as we just looked at, we only need to return the length.

With the example, we could easily think of a recursive solution starting with zero indexes and going down all the different paths. Using this array [0,3,1,6,2,2,7], we could take, for instance, with 0, we can go to 3, or we can go to 1 or go to 6.

And then, from that point on, recursively keep continuing. Look at the following example, which path is the longest that’s going to be exponential; we can easily think there has to be some dynamic programming approach.

So, we have an array, and each of these indexes has at least one length.

[0,3,1,6,2,2,7]
[1,1,1,1,1,1,1]

We will start at the first index, 0, whose length is 1, but with 3, we can look behind and if 3 is bigger than 0, then 3 has 2 lengths. If we go with 1 again, we will look behind all the indexes before the current index.

From the zero indexes, we can see that 1 is greater than 0, but 1 is not greater than 3, so at this point, we are calculating 0 and 1, and their length would be 2.

[0,3,1,6,2,2,7]
[1,2,2,1,1,1,1]

While considering 6, let’s look at behind from the start, we know 6 is greater than [0,1] or [0,3], and including 6, its length would be 3 then also the length of 2 is 3, and so on, this is a squared approach.

[0,3,1,6,2,2,7]
[1,2,2,3,3,...]

Time Complexity and Space Complexity

Let’s jump into the code and create our class called CalculateSubSequence; inside the lengthOfLIS function, we initialize our nums_list variable to be the length of nums with an array that is going to be just 1 time.

Inside the nested loops, we will check whether the value is bigger than the number we are checking. Then, let’s take our nums_list of i, and we will update the nums_list value while taking the max value using nums_list[i].

i comes after iterating from the outer loop, and for nums_list[j], the j comes after iterating from the inner loop then we add 1 with it. In the end, we are returning the max value of nums_list.

class CalculateSubSequence:
    def lengthOfLIS(self, nums: list[int]) -> int:

        nums_list = [1] * len(nums)

        for i in range(len(nums) - 1, -1, -1):

            for j in range(i + 1, len(nums)):

                if nums[i] < nums[j]:

                    nums_list[i] = max(nums_list[i], nums_list[j] + 1)

        return max(nums_list)


sbs = CalculateSubSequence()
sbs.lengthOfLIS([0, 3, 1, 6, 2, 2, 7])

Here time complexity will be n squared, and the space complexity will be o of n.

4

The above solution is enough, but another approach, n log, uses a binary search to the left side of our temporary array using bisect_left.

from bisect import bisect_left


class CalculateSubSequence:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        tmp = [nums[0]]
        for n in nums:
            x = bisect_left(tmp, n)
            if x == len(tmp):
                tmp.append(n)
            elif tmp[x] > n:
                tmp[x] = n
        return len(tmp)


sbs = CalculateSubSequence()
sbs.lengthOfLIS([0, 3, 1, 6, 2, 2, 7])

Output:

4