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.
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)
How to execute the code?
Make sure you have python install. Open terminal and type command
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.
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.