Length of Longest Increasing Subsequence (LIS) in python [Dynamic Programming]

The LIS or longest increasing subsequence means to find a subsequence in list of numbers in which the subsequence’s elements are in ascending order and in which the subsequence is as long as possible. This subsequence does not have to be continuous. Here we have to find the length of the longest increasing subsequence.

We will be solving for Length of Longest Increasing Subsequence (LIS) in python.

Algorithms: Binary Search Tree and its functionality in python

Lets take an example first.

0 7 5 11 3 10 6 14 1 9 5 13 3 11 7 15

Here length of longest increasing subsequence is 6. [0,3,6,9,11,15]

Now we will be solving this problem using dynamic problem solution. Lets first look at the code and then we will discuss what is it doing.

def longest_increasing_subsequence(numbers):
    temp_list = [1 for x in range(0,n)]
    i,j = 1,0
    while i<len(numbers) and j<len(numbers):
        if numbers[j]<numbers[i]:
            if temp_list[j]+1>temp_list[i]:
                temp_list[i] = temp_list[j]+1
        j=j+1
        if j==i:
            j,i=0,i+1
    return max(temp_list)

if __name__ == '__main__':
    n = int(input())
    numbers = []
    for i in range (0,n):
    numbers.append(int(input()))
    print longest_increasing_subsequence(numbers)

If you want to learn data structures in python you can read the below books.

How to execute the code?

Make sure you have python install. Open terminal and type command

python filename.py

And then give input as below.

16  // Number of elements to be entered.
0   //list of number 
8
4
12
2
10
6
14
1
9
5
13
3
11
7
15

Output will be like this

6 //Length of Longest Increasing Subsequence (LIS)

What algorithm we used here?

We used dynamic programming for this problem.  Lets find out the overlapping subproblem here which will be solved again and again. Let take an example of list with length 3. Below are the list of problem that we will be solving. We can solve them and save them.

           
      lis(3) 
     /     |      
   lis(2) lis(1) 
   /
lis(1)

We can see there are recurring problem that is lis(1). We can save them and use it instead of calculating every time. Lets see how we implemented it.

Algorithms: Mirror a Binary tree using python

Solution Explanation

We will keep a list of length of the list that is provided say n=5 and fill it with one.

temp_list = [1,1,1,1,1]

Now we will start to loop through the given number with two of our variable i=1 and j=0;

If number[i] is greater than number[j] 
and value at temp[j]+1 greater than temp[i]
we will change the value of temp[i] to temp[j]+1

What this is says that if there is a number on ith position which is greater than the number at jth position, this means that this number can be used in longest increasing subsequence and thus we increased the value at jth position by one and place it at ith position.

We only increase the value if the value at jth position + 1 is greater than value at ith position to make sure that it has the length of the longest subsequence.

In this way on each location in our temp_list we will get the length of longest subsequence that can be made by using the element at that position. Now to get the longest we will just have to find the maximum of this list temp_list.

If you like the article please share and subscribe to keep us motivated. More algorithms in python you can find here.

Algorithms: Coding a linked list in python

Level order traversal of a binary tree in python.

---