You are given a sequence. You have to find the length of the longest subsequence of the given sequence such that all the elements of that subsequence are sorted or are in increasing order. A subsequence is a smaller sequence that is made by eliminating or deleting some elements from the initial sequence but not in any specific manner, i.e., it is not necessary that the removal of elements should follow a specific pattern.
Example 1:
Input: nums = [12,9,2,5,3,7,65,22] Output: 4
Explanation: If you clearly see the line in this example is [2,3,7,65], therefore the length is 4.
Example 2:
Input: nums = [60, 3, 10, 7, 40, 95] Output: 4
Explanation: Here in this example, the possible longest increasing subsequence is [3, 7, 40, 95]; therefore, the length is 4.
Example 3:
Input: nums = [9,9,9,9,9,9,9] Output: 1
Explanation:
Since all the elements are equal, i.e., 9 in this example, the length of the list
lis
will be 1
Approach 1: Recursive Approach
In this approach, we are using the optimal substructure property of the problem and will be solving the problem by breaking it into smaller substructures. Here, for finding the list of any index i, i.e. lis(index), we will recursively find the list up till index - 1.
lis(index) = 1 + maximum(lis(j)), where j belongs to (0, i) && arr[j] < arr[i] OR lis(index) = 1, if there exists no index j satisfying the above condition. Let the input index be L.
The max(L[i]) will be the longest increasing subsequence or lis where 0<i<n, where n is the size of the array.
Algorithm
- Create an array.
- Return 1 if the array is NULL.
- If the array is not NULL, initialize a variable max_ending to store the initial list as 1.
-
Keep track of two things:
- max_ending: length of longest increasing subsequence having the last element as arr[n - 1].
- max_ref: variable to store the maximum length of the lis, as it’s not necessary that lis has the last element as arr[n - 1].
- find recursively the length of all lis with the last element as arr[i], (i is from 1 -> n).
- Compare this result and update the max_ending variable.
- Finally compare the max_ref, having the maximum length of lis, with max_ending, and update the result.
- Return the result.
The implementation of the above-discussed approach is:
C++ Programming
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
// function to recursively find the length of the
// longest increasing subsequence.
// here we keep track of two things:
/*
...1. max_ending: length of longest increasing subsequence
having the last element as arr[n - 1].
...2. max_ref: variable to store the maximum
length of the lis, as it's not necessary that lis
has the last element as arr[n - 1].
*/
int lisLength( int arr[], int n, int *max_ref)
{
// Base case
if (n == 1)
return 1;
// max-ending variable to store
// lis length with last element as arr[n - 1]
int res, max_ending_here = 1;
// find recursively the length of all lis
// with the last element as arr[i], (i is from 1 -> n).
// compare this result and update max_ending variable.
for (int i = 1; i < n; i++)
{
res = lisLength(arr, i, max_ref);
if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)
max_ending_here = res + 1;
}
// finally comparing the max_ref, having the maximum length
// of lis, with
// max_ending,
// and update the result.
if (*max_ref < max_ending_here)
*max_ref = max_ending_here;
// return the result, i.e. the length of lis
return max_ending_here;
}
// a function to wrap lisLength()
int lis(int arr[], int n)
{
// to store the result
int max = 1;
lisLength( arr, n, &max );
// returns the result
return max;
}
int main()
{
int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
int n = sizeof(arr)/sizeof(arr[0]);
cout << "The length of the longest increasing subsequence is:\n";
cout << lis( arr, n );
return 0;
}
Output
The length of the longest increasing subsequence is: 6
Java Programming
class LIS
{
static int max_ref; // to hold the maximum length of lis
// method to recursively find the length of the
// longest increasing subsequence.
// here we keep track of two things:
/*
...1. max_ending: length of longest increasing subsequence
having the last element as arr[n - 1].
...2. max_ref: variable to store the maximum
length of the lis, as it's not necessary that lis
has the last element as arr[n - 1].
*/
static int lisLength(int arr[], int n)
{
// base case
if (n == 1)
return 1;
// max-ending variable to store
// lis length with last element as arr[n - 1]
int res, max_ending_here = 1;
// find recursively the length of all lis
// with the last element as arr[i], (i is from 1 -> n).
// compare this result and update max_ending variable.
for (int i = 1; i < n; i++)
{
res = lisLength(arr, i);
if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)
max_ending_here = res + 1;
}
// finally comparing the max_ref, having the maximum length
// of lis, with
// max_ending,
// and update the result.
if (max_ref < max_ending_here)
max_ref = max_ending_here;
// return the result, i.e. the length of lis
return max_ending_here;
}
//a method to wrap lisLength()
static int lis(int arr[], int n)
{
// to store the result
max_ref = 1;
lisLength( arr, n);
// returns the result
return max_ref;
}
public static void main(String args[])
{
int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
int n = arr.length;
System.out.println("The length of the longest increasing subsequence is:\n"
+ lis(arr, n));
}
}
Output
The length of the longest increasing subsequence is: 6
Python
# method to recursively find the length of the
# longest increasing subsequence.
# here we keep track of two things:
"""
...1. max_ending: length of the longest increasing subsequence
having the last element as arr[n - 1].
...2. max_ref: variable to store the maximum
length of the lis, as it’s not necessary that lis
has the last element as arr[n - 1].
"""
# to hold the maximum length of lis
global maximum
def lisLength(arr , n ):
# for accessing the global variable
global maximum
# Base Case
if n == 1 :
return 1
# max-ending variable to store
# lis length with last element as arr[n - 1]
maxEndingHere = 1
# find recursively the length of all lis
# with the last element as arr[i], (i is from 1 -> n).
# compare this result and update max_ending variable.
for i in range(1, n):
res = lisLength(arr , i)
if arr[i-1] < arr[n-1] and res+1 > maxEndingHere:
maxEndingHere = res +1
# finally comparing the max_ref, having the maximum length
# of lis, with
# max_ending,
# and update the result.
maximum = max(maximum , maxEndingHere)
# return the result, i.e. the length of lis
return maxEndingHere
def lis(arr):
# for accessing the global variable
global maximum
# length of arr
n = len(arr)
# to store the result
maximum = 1
# The function lisLength() stores its result in maximum
lisLength(arr , n)
# returns the result
return maximum
arr = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
n = len(arr)
print ("The length of the longest increasing subsequence is:")
print (lis(arr))
Output
The length of the longest increasing subsequence is: 6
Complexity Analysis
- Time Complexity : The time complexity of the above approach is exponential because this approach includes the overlapping of subproblems.
- Space Complexity: O(1), as apart from the internal stack, no additional space is utilized
Approach 2: Dynamic Programming
This approach is better than the previous approach. The above approach involves overlapping subproblems, which takes a lot of time. This approach involves memoization which results in avoiding repeated computation of subproblems.
Algorithm
- Create a DP array of size n.
- Find the length of the longest increasing subsequence maintaining the DP.
- Calculating the values of lis in a bottom-up fashion.
- For every index, i, set its initial lis value as 1.
- Return the result, i.e., the largest element in lis[].
The implementation of the above-discussed approach is:
C++ Programming
#include<bits/stdc++.h>
using namespace std;
// function to find the length of the
// longest increasing subsequence
// maintaining a dp.
int lisLength( int arr[], int n )
{
int lis[n];
lis[0] = 1;
// calculating the values of lis
// in bottom-up fashion.
for (int i = 1; i < n; i++ )
{
// for every index i,
// set its initial lis value as 1
lis[i] = 1;
for (int j = 0; j < i; j++ ) if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
}
// return the result, i.e.
// the largest element in
// lis[].
return *max_element(lis, lis+n);
}
int main()
{
int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
int n = sizeof(arr)/sizeof(arr[0]);
cout << "The length of the longest increasing subsequence is:\n" << lisLength( arr, n );
return 0;
}
Output
The length of the longest increasing subsequence is: 6
Java Programming
class LIS
{
// method to find the length of the
// longest increasing subsequence
// maintaining a dp.
static int lisLength(int arr[],int n)
{
int lis[] = new int[n];
int i,j,max = 0;
// for every index i,
// set its initial lis value as 1
for ( i = 0; i < n; i++ )
lis[i] = 1;
// calculating the values of lis
// in bottom-up fashion.
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ ) if ( arr[i] > arr[j] &&
lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
// return the result, i.e.
// the largest element in
// lis[].
for ( i = 0; i < n; i++ )
if ( max < lis[i] )
max = lis[i];
return max;
}
public static void main(String args[])
{
int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
int n = arr.length;
System.out.println("The length of the longest increasing subsequence is:");
System.out.print(lisLength( arr, n ));
}
}
Output
The length of the longest increasing subsequence is: 6
Python
# function to find the length of the
# longest increasing subsequence
# maintaining a dp.
def lisLength(arr):
n = len(arr)
# for every index i,
# set its initial lis value as 1
lis = [1]*n
# calculating the values of lis
# in bottom-up fashion.
for i in range (1 , n):
for j in range(0 , i):
if arr[i] > arr[j] and lis[i]< lis[j] + 1 :
lis[i] = lis[j]+1
maximum = 0
# return the result, i.e.
# the largest element in
# lis[].
for i in range(n):
maximum = max(maximum , lis[i])
return maximum
# end of lisLength function
# Driver program to test above function
arr = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
print "The length of the longest increasing subsequence is:"
print lisLength(arr)
Output
The length of the longest increasing subsequence is: 6
Complexity Analysis
- Time Complexity : O(n^2), as we are using a loop to compute the LIS in this approach.
- Space Complexity: O(n), as we are using an array of size n.
Approach 3: Optimised Dynamic Programming
This approach is the most optimized approach among all three approaches. In this method, we iterate over the array from left to right. We will create a dp array as well whose all elements will be initialized as 0. The DP will be used to store the increasing subsequence. All the elements will be placed at their correct position using Binary Search. It is important to remember that for Binary Search, we will iterate over only that part of our dp array in which we have made the changes by adding some elements at their correct indices.
Let’s understand the above approach with an example for a better understanding:
Consider the sequence input: [0, 9, 4, 12, 1] dp: [0] dp: [0, 9] dp: [0, 4] dp: [0, 4, 12] dp: [0, 1, 12] This is clearly not the longest possible increasing subsequence of the given subsequence, but this length of dp array is the length of the Longest Increasing Subsequence
Algorithm
- Create a DP array.
- Maintain a dp array whose all elements will be initialized as 0.
- Implement binary search to determine the correct position of an element.
- Store the increasing subsequence created by including the currently existing element in the dp array.
- Create space for other greater elements than the currently found element and place the element in its correct position in the dp using the binary search function.
- Return the dp array.
The implementation of the above-discussed approach is:
C++ Programming
#include <iostream>
#include <vector>
// function to implement binary search
// to determine the correct position of
// an element.
int binarySearch(std::vector& v, int l, int r, int key)
{
while (r - l > 1) {
int m = l + (r - l) / 2;
if (v[m] >= key)
r = m;
else
l = m;
}
return r;
}
int lisLength(std::vector& v)
{
if (v.size() == 0)
return 0;
std::vector tail(v.size(), 0);
int length = 1;
tail[0] = v[0];
for (size_t i = 1; i < v.size(); i++) {
// new smallest value
if (v[i] < tail[0]) tail[0] = v[i]; // largest subsequence extended by v[i] else if (v[i] > tail[length - 1])
tail[length++] = v[i];
// v[i] will be the last element of the current subsequence
// so to create space for other greater elements than v[i]
// and place v[i] in its correct position in the dp
// using the binary search function.
else
tail[binarySearch(tail, -1, length - 1, v[i])] = v[i];
}
return length;
}
int main()
{
std::vector v{ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
std::cout << "The length of the longest increasing subsequence is:\n"
<< lisLength(v);
return 0;
}
Output
The length of the longest increasing subsequence is: 6
Java Programming
import java.io.*;
import java.util.*;
import java.lang.Math;
class LISlength {
// method to implement binary search
// to determine the correct position of
// an element.
static int binarySearch(int A[], int l, int r, int key)
{
while (r - l > 1) {
int m = l + (r - l) / 2;
if (A[m] >= key)
r = m;
else
l = m;
}
return r;
}
static int lisLength(int A[], int size)
{
int[] tailTable = new int[size];
int len;
tailTable[0] = A[0];
len = 1;
for (int i = 1; i < size; i++) {
if (A[i] < tailTable[0]) // new smallest value tailTable[0] = A[i]; else if (A[i] > tailTable[len - 1])
// largest subsequence extended by A[i]
tailTable[len++] = A[i];
else
// v[i] will be the last element of the current subsequence
// so to create space for other greater elements than v[i]
// and place v[i] in its correct position in the dp
// using the binary search method.
tailTable[binarySearch(tailTable, -1, len - 1, A[i])] = A[i];
}
return len;
}
public static void main(String[] args)
{
int A[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
int n = A.length;
System.out.println("The length of the longest increasing subsequence is:");
System.out.print(lisLength(A, n));
}
}
Output
The length of the longest increasing subsequence is: 6
Python Programming
# function to implement binary search
# to determine the correct position of
# an element.
def binarySearch(A, l, r, key):
while (r - l > 1):
m = l + (r - l)//2
if (A[m] >= key):
r = m
else:
l = m
return r
def lisLength(A, size):
tailTable = [0 for i in range(size + 1)]
len = 0
tailTable[0] = A[0]
len = 1
for i in range(1, size):
if (A[i] < tailTable[0]): # new smallest value tailTable[0] = A[i] elif (A[i] > tailTable[len-1]):
# largest subsequence extended by A[i]
tailTable[len] = A[i]
len+= 1
else:
# v[i] will be the last element of the current subsequence
# so to create space for other greater elements than v[i]
# and place v[i] in its correct position in the dp
# using the binary search method.
tailTable[binarySearch(tailTable, -1, len-1, A[i])] = A[i]
return len
# Driver program to
# test above function
A = [ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 ]
n = len(A)
print("The length of the longest increasing subsequence is:")
print(lisLength(A, n))
Output
The length of the longest increasing subsequence is: 6
Complexity Analysis
- Time Complexity : O(n*(log n)), because we are iterating the loop n time, and in the worst case, we will be using binary search to search the element, which will take log n time.
- Space Complexity: O(n), as we are using a DP array of size n.
Wrapping Up!
In this article, we have learned an amazing concept of Dynamic Programming. Dynamic Programming is one of the most important data structures and is usually asked in the top interview questions as well. “Longest Increasing Subsequence” is a popular as well as a very important problem that has been asked in various interview questions. We also discussed three well-explained approaches along with some suitable examples to solve this problem:
- Using Recursion
- Using Dynamic Programming
- Using Optimised Dynamic Programming
We also covered in detail how all three of the approaches work and their significance of them respectively. We discussed their time complexity as well as space complexity along with a proper explanation. Different programmers prefer different languages for coding. So, we made sure that all our readers could refer to this article.
That’s why this article also contains well-explained codes for all the approaches in the three most popular languages, which are c++, Java, and Python, along with their respective outputs attached to the article for a better understanding for a wide range of our readers. We sincerely hope that this article has walked you through some deep and important concepts of DP and how we should approach such kinds of problems. We surely wish you to keep up your practice and crack all the questions easily. With this, we are wrapping up this article.
Happy Learning!
People are also reading:
Leave a Comment on this Post