Find Longest Increasing Subsequence in Python

In this tutorial, we will shortlist the longest sequence of increasing numbers from the given sequence of numbers using Python. We will use the Binary Search algorithm to increase the speed of the code for this purpose. The logic is that we will first find the lower and upper boundary values of the given sequence.  And finally, shortlist the increasing sequence.

Binary Search Algorithm:

This is a searching algorithm that could be applied to a sorted list. Here, what we do is we first initiate the upper and lower boundary of the search to be min and max value of the list. then if the middle value is less than the max value we iterate the upper boundary to mid-value and then treat this half list as a new search sphere. In this way, on each iteration, the searching sphere reduces to half which reduces the time complexity (O(logn)) of search and increases the speed of the code.

Function to Rule:

Here, we will discuss the function to be used for the above implementation.

In the Python shell, we will define a function named “subsequence” and give it “sea” as input. We will first take a condition of no sequence given. For that, it will return “seq” i.e. no subsequence.

def subsequence(seq):
    if not seq:
        return seq

 

Now we will define two lists of the length of a given sequence and initiate a variable L and the first value of sequence M to be 1 and 0 respectively.

M = [None] * len(seq)    
P = [None] * len(seq)

 

Now we will loop through the sequence to find the lower and upper value for our binary algorithm. Inside the loop, we have first initiated the lower and upper values.

L = 1
M[0] = 0

 

After this, we will apply a binary search algorithm to minimize the searching sphere by constantly iterating the upper and lower values.

for i in range(1, len(seq)):
    lower = 0
    upper = L

    if seq[M[upper-1]] < seq[i]:
        j = upper

    else:
        while upper - lower > 1:
            mid = (upper + lower) // 2
            if seq[M[mid-1]] < seq[i]:
                lower = mid
            else:
                upper = mid

        j = lower    

    P[i] = M[j-1]

    if j == L or seq[i] < seq[M[j]]:
        M[j] = i
        L = max(L, j+1)

 

In last we will initiate a list named “r”. Then iterate through the sequence to fill the results list.

r = []
pos = M[L-1]
for _ in range(L):
    r.append(seq[pos])
    pos = P[pos]

return r[::-1]

 

Complete Code:

Here we will apply the given function on a sequence to check the output, in Python.

Given Sequence:

[1,2,56,32,76,67,98]

def subsequence(seq):
    if not seq:
        return seq

    M = [None] * len(seq)   
    P = [None] * len(seq)

    L = 1
    M[0] = 0

    for i in range(1, len(seq)):
        lower = 0
        upper = L

        if seq[M[upper-1]] < seq[i]:
            j = upper

        else:
            while upper - lower > 1:
                mid = (upper + lower) // 2
                if seq[M[mid-1]] < seq[i]:
                    lower = mid
                else:
                    upper = mid

            j = lower    

        P[i] = M[j-1]

        if j == L or seq[i] < seq[M[j]]:
            M[j] = i
            L = max(L, j+1)

    r = []
    pos = M[L-1]
    for _ in range(L):
        r.append(seq[pos])
        pos = P[pos]

    return r[::-1]  
  
seq=[1,2,56,32,76,67,98]
subsequence(seq)

 

Output:

[1,2,32,67,98]

 

Leave a Reply