Longest increasing subsequence or LIS problem is a classical dynamic programming problem which refers to finding the length of the longest subsequence from an array such that all the elements of the sequence are in strictly increasing order.
Formally for an array A[ ] of length N, having indices i1, i2, i3,...iN, longest increasing subsequence will be { A[ i1], A[ i2], A[ i3], …,A[ ik] }, where i1 < i2 < i3 < ...ik and A[ i1] < A[ i2] < A[ i3] < …A[ ik]
Note : A subsequence is a sequence which can be obtained from an array by removing some or no elements, without changing the order of elements.
For example, for the given sequence {2, 5, 3, 7, 11, 8, 10, 13, 6 } , length of longest increasing subsequence will be 6 and longest increasing subsequence will be { 2, 5, 7, 8, 10, 13 } or { 2, 3, 7, 8, 10, 13} as both subsequences are strictly increasing and have length equal to 6, which is the maximum possible length of longest LIS.
Longest Increasing Subsequence Using Dynamic Programming
Approach:
We can use dynamic programming to solve this problem. Let’s construct a LIS[ ] array, which contains the length of longest increasing subsequence ending at position i.
LIS[ 0] will be 1, and for each i>0, LIS[ i ], which will be calculated on the basis of LIS[ i-1 ], LIS[ i-2 ],...LIS[ 0 ].
For calculating LIS[ i ], we will traverse the LIS[ ] array from j=0 to j<i, and LIS[ i ] will be the maximum of current LIS[ i ] and LIS[ j ] +1.
The above approach finds the length of LIS, for restoring the sequence we can use a parent array,whose elements are initially assigned to -1.The parent array stores the index j at which the value LIS[ j ] +1 was maximum.
Pseudo code :
For i=0 to N-1
For j=0 t0 i-1
If A[ j ] <A[ i ]
If LIS[ i ]<LIS[ j ]+1
LIS[ i ] = LIS[ j ]+1
Parent[ i ]=j
Print max value in LIS array
Explanation:
For calculating LIS[ i ], traverse array A[ ] from 0 to i-1, if there is an element A[ j ], which is smaller than A[ i ], then LIS[ i ] will be maximum of LIS[ j ]+1 and LIS[ i ].
This works because LIS[ j ] contains the length of longest increasing subsequence ending at position j, and also A[ j ]< A[ i ], then adding A[ i ] to the subsequence ending at position j, will increase the subsequence length by 1. If LIS[ i ] is already greater than LIS[ j ]+1, then we will not add A[ i ] to the subsequence ending at j.
Length of Longest increasing subsequence will be the maximum value in LIS[ ] array.
Code:
- C++
- Python
#include <bits/stdc++.h>
using namespace std;
// function for finding length of
// longest increasing subsequence
void longest_increasing_subsequence(int a[], int n)
{
int lis[n];
int parent[n];
// initialize lis with 1 as each element
// has a subsequence length equal to 1
fill(lis, lis + n, 1);
// initialize parent with -1
fill(parent, parent + n, -1);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (a[j] < a[i])
if (lis[i] < lis[j] + 1)
{
lis[i] = lis[j] + 1;
parent[i] = j;
}
}
}
int length = 0, pos = 0;
// length of subsequence is the maximum value
// in lis array
for (int i = 0; i < n; i++)
if (length < lis[i])
{
length = lis[i];
pos = i;
}
cout << "Length of longest increasing subsequence " << length << endl;
// restoring the sequence
// for storing longest increasing subsequence
vector<int> sequence;
while (pos != -1)
{
sequence.push_back(a[pos]);
pos = parent[pos];
}
reverse(sequence.begin(), sequence.end());
for (auto x : sequence)
cout << x << " ";
}
// Driver code
int main()
{
int a[9] = {2, 5, 3, 7, 11, 8, 10, 13, 6};
int n = sizeof(a) / sizeof(int);
// function calling
longest_increasing_subsequence(a, n);
}
Complexity analysis:
For calculating LIS[ i ] value for each i in range of N, we traverse the LIS[ ] array from j=0 to j<i.
N iterations are done in the first loop and 1, 2, 3, 4,....N iterations are done for each i in the first loop.
Thus the complexity is $N*(1+ 2+ 3+ 4...N)= O(N^2)$
Time complexity for the above approach is $O( N^2 )$, we can use a better approach by constructing a different dynamic programming solution which uses binary search for optimization.
Longest Increasing Subsequence Using Divide and Conquer
Let’s take a temporary array temp[ ]. Now we will traverse the array A[ ] and fill temp[ ] array using the following rules :
- If A[ i ] is greater than the last element in temp[ ] array, append it to the temp array,
- Else if A[ i ] is smaller than or equal to the last element in the temp array, put A[ i ] to an index j in temp[ ] such that, temp[ j-1 ]< A[ i ] and remove all elements in temp[ ] after index j.
We will find the appropriate position of A[ i ] using binary search as the temp[ ] array will always be sorted.
By filling the temp[ ] array this way, at temp[ i ] we are storing the element of array A[ ] at which a subsequence of length i ends.
Since the array temp[ ] will always be sorted in increasing order, for getting an appropriate position for putting A[ i ] in array temp[ ], if it is smaller than or equal to the last value in temp[ ] array, we will use modified binary search.
This binary search function will return the position of the first element which is greater than or equal to A[ i ].
For restoring the subsequence from length, we will use a position array, Position[ ], which will store the index of the element stored at temp[ i ] for all i in the range of length of longest increasing subsequence.
Implementation of above approach:
- C++
- Python
#include <bits/stdc++.h>
using namespace std;
// Function for getting index of first
// element which is greater than or equal
// to A[ i ]
int search_id(int arr[], int N, int X)
{
int mid;
// Initialise starting index and
// ending index
int low = 0;
int high = N;
// Till low is less than high
while (low < high)
{
mid = low + (high - low) / 2;
// If X is less than or equal
// to arr[mid], then find in
// left subarray
if (X <= arr[mid])
{
high = mid;
}
// If X is greater arr[mid]
// then find in right subarray
else
{
low = mid + 1;
}
}
// Return the lower_bound index
return low;
}
// function for finding length of
// longest increasing subsequence
void longest_increasing_subsequence(int a[], int n)
{
int temp[n];
// position array will store the index of
// element stored at ith position in temp
// array
int position[n];
// initialize temp array with INT_MAX
// as all values in array a will be smaller than
//INT_MAX
fill(temp, temp + n, INT_MAX);
//Variable to track position of last element
// in temp array
int pt = 0;
temp[0] = a[0];
position[0] = 0;
for (int i = 1; i < n; i++)
// append a[i] if it is greater
// then last value in temp array
if (temp[pt] < a[i])
temp[pt + 1] = a[i], position[pt + 1] = i, pt++;
else
{
// if a[i] is greater, put it in appropriate position
// such that temp[ind-1]<a[i]
int ind = search_id(temp, n, a[i]);
temp[ind] = a[i];
position[ind] = i;
}
// Number of elements in temp array is
// is the length of longest increasing subsequence
cout << "Length of longest increasing subsequence " << pt + 1 << endl;
for (int i = 0; i < pt + 1; i++)
cout << a[position[i]] << " ";
}
// Driver code
int main()
{
int a[9] = {2, 5, 3, 7, 11, 8, 10, 13, 6};
int n = sizeof(a) / sizeof(int);
// function calling
longest_increasing_subsequence(a, n);
}
Complexity analysis:
Array A[ ] is traversed once for all i in range N and, for each A[ i ], function search_id( ) is called.
Function search_id( ) uses binary search for calculating the index of lower bound of current A[ i ] and binary search has time complexity of $O( \log{N} )$, as search space is halved every time entering the loop.
Overall time complexity:
$N*logN= O( N(\log{N}) )$