Table of Contents
Problem Statement
You are given an array of integers. The problem “Construction of Longest Increasing Subsequence (N log N)” asks to construct the longest increasing subsequence.
Example
arr[]={1, 4, 7, 2, 9, 6, 12, 3 }12, 9, 7, 4, 1 and the size of this longest increasing subsequence is 5.
Explanation
We find out the longest subsequence that is increasing in an array.
Algorithm for Construction of Longest Increasing Subsequence (N log N)
1. Create two arrays lastIndexes and firstIndexes of size n, and initialize both of the arrays with 0 and -1 respectively.
2. Traverse the array from 1 to n(length of the array).
1. Check if the current array element is less than the arr[lastIndexes[0]], if true, then update lastIndexes[0]=1.
2. Check if the arr[i] is greater than the arr[lastIndexes[leng-1]], do the following
1. Set the firstIndexes[i] to lastIndexes[leng-1].
2. lastIndexes[leng++] = i.
3. Else get the position of arr[i] using binary search and do the following.
1. Update the value at firstIndexes[i] to lastIndexes[position-1].
2. Update the value of the lastIndexes[position] to i.
3. Print the array, by initializing the value of i to the firstIndexes[i].Explanation
We have given an array of integers and we have asked to construct the longest increasing subsequence. For this, we will be using two arrays lastIndexes and firstIndexes and fill it with the value of 0 and -1 respectively. firstIndexes array will be initialized as 1. Because this will be storing the values as positions as indexes. We will be updating the values while traversing the array.
We are going to traverse the array from 1 to n. Where n is the length of the array. While traversing, array lastIndexes will be used as a position or index of an array. We will check some conditions we are going to check if the current array element is less than the array of lastIndexes[leng-1]. Length is initially defined as 1, which means at least we will have the subsequence of length 1. So if the above condition is true then update the lastIndexes[0] to 1.
We need to check if the arr[i] is greater than the array of lastIndexes[n-1]. Then update both of the arrays, set firstIndexes[i] to last value of lastIndexes[n-1] and lastIndexes[leng] to i and increase the value of leng value. Else we have to find out the current array element position. For this, we will be using the binary search and get that index to the position. And update the value of lastIndexes[position-1] to firstIndexes[i] and lastIndexes[position] to i.
After the traversal we need to print the array. For this we will traversing from the last to 0th position and initializing each index to firstIndexes[i] after every traversal and print each possible value of the array.
Code
C++ code for Construction of Longest Increasing Subsequence (N log N)
#include<iostream>
#include<vector>
using namespace std;
int GetPosition(int arr[], vector<int>& T, int left, int right,int key)
{
while (right - left > 1)
{
int mid = left + (right - left) / 2;
if (arr[T[mid]] >= key)
right = mid;
else
left = mid;
}
return right;
}
int LongestIncreasingSubsequence(int arr[], int n)
{
vector<int> lastIndexes(n, 0);
vector<int> firstIndexes(n, -1);
int len = 1;
for (int i = 1; i < n; i++)
{
if (arr[i] < arr[lastIndexes[0]])
{
lastIndexes[0] = i;
}
else if (arr[i] > arr[lastIndexes[len - 1]])
{
firstIndexes[i] = lastIndexes[len - 1];
lastIndexes[len++] = i;
}
else
{
int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
firstIndexes[i] = lastIndexes[positon - 1];
lastIndexes[positon] = i;
}
}
cout << "Longest Increase Subsequence:" << endl;
for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
cout << arr[i] << " ";
cout << endl;
cout<<"LIS size:\n";
return len;
}
int main()
{
int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<< LongestIncreasingSubsequence(arr, n);
return 0;
}
Longest Increase Subsequence: 12 9 7 4 1 LIS size: 5
Java code for Construction of Longest Increasing Subsequence (N log N)
import java.util.Arrays;
class LongestIncreasingSubsequence
{
public static int GetPosition(int arr[], int T[], int left, int right, int key)
{
while (right - left > 1)
{
int mid = left + (right - left) / 2;
if (arr[T[mid]] >= key)
right = mid;
else
left = mid;
}
return right;
}
public static int getSubsequence(int arr[], int n)
{
int lastIndexes[] = new int[n];
Arrays.fill(lastIndexes, 0);
int firstIndexes[] = new int[n];
Arrays.fill(firstIndexes, -1);
int len = 1;
for (int i = 1; i < n; i++)
{
if (arr[i] < arr[lastIndexes[0]])
lastIndexes[0] = i;
else if (arr[i] > arr[lastIndexes[len - 1]])
{
firstIndexes[i] = lastIndexes[len - 1];
lastIndexes[len++] = i;
}
else
{
int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
firstIndexes[i] = lastIndexes[positon - 1];
lastIndexes[positon] = i;
}
}
System.out.println("Longest Increasing Subsequence of given input");
for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
System.out.print(arr[i] + " ");
System.out.println();
return len;
}
public static void main(String[] args)
{
int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
int n = arr.length;
System.out.print("LIS size:\n" + getSubsequence(arr, n)+"\n");
}
}
Longest Increasing Subsequence of given input 12 9 7 4 1 LIS size: 5
Complexity Analysis
Time Complexity
O(n log n) where “n” is the number of elements in the array. Since we have used the binary search which gives us a logarithmic factor. But if we had to call the binary search for each index. Then in the worst case, the time complexity will be O(N log N).
Space Complexity
O(n) where “n” is the number of elements in the array. As we have created two temporary arrays firstIndexes and lastIndexes. The space complexity becomes O(N).