Do you think IIT Guwahati certified course can help you in your career?
Introduction
This article will discuss the dynamic programming approach of the Longest Increasing Subsequence problem having O(n log n) complexity.
To better understand the longest increasing subsequence problem, it is recommended to go through the first part of the article, which covers the recursive solution and a dynamic programming solution of O(n2) time complexity. This article will solve the LIS problem in O(n log n) time complexity.
To solve the longest increasing subsequence in O(n log n) time, we will use dynamic programming and the upper_bounds function provided in the standard C++ library.
This article requires some prior knowledge of Dynamic Programming. Readers with no previous knowledge of this paradigm can read this article: Dynamic Programming & algorithms.
The second part of the Longest Increasing Subsequence article covers the highly optimized solution having O(n log n) complexity obtained by dynamic programming. The first part of the article covers the naive recursive solution and a semi-optimized dynamic programming solution. You can find the first part of the article here.
Given an input array, find the length of the longest increasing subsequence such that all the elements of the subsequence are sorted in strictly increasing order.
A subsequence is said to be strictly increasing if each element of the subsequence is greater than its preceding element.
The code takes an input array of size n. The output is the length of the longest increasing subsequence.
Sample input:
10 5 8 3 9 4 12 11
Sample output:
4
The LIS can be {5, 8, 9, 11} or {5, 8, 9, 12}.
Approach and Explanation
We will first create a dp array of size (n+1).
Here, the dp table’s significance is that the dp table’s index acts as our counter variable that denotes the size of the increasing subsequence. Thus dp[3] means that the length of our LIS is 3. Similarly, dp[5] represents the length of our LIS is 5.
Initialize the 0th index to negative infinity (INT32_MIN) and the rest to positive infinity (INT32_MAX).
We then iterate through the array from 0 up to size. For each iteration, we calculate upper_bound by:
int idx = upper_bound(dp,dp+size+1,input[i]) - dp.
We perform Binary Search in this step. The expression searches for the element input[i] in the dynamic table dp in the range [0, size+1] and returns the index of the element in the dp array.
We then decide where to place the idx element in our dp table. To do so, we put two checks-
dp[idx-1] < input[i]: This ensures that the last element is the greatest element of the increasing subsequence.
dp[idx] > input[i]: This ensures that the first element is the smallest element of the increasing subsequence.
These checks ensure that the first and the last elements are the smallest and the greatest values, respectively. We do so because we want to broaden the range of our increasing subsequence and find the desired LIS length.
On completion of our for loop, we create a variable maxLength and initialize its value to 0.
We again iterate through the dp table. This time we start from the end index up to the 0th index. We check for the first non-infinity value.
Why do we do so, you may ask? Let us take our input array example. Once the code execution is complete, the elements of dp are {INT32_MIN, 3, 4, 9, 11, INT32_MAX, INT32_MAX, INT32_MAX}. The first non-infinity number is 11, which is present at dp[4]. By iterating from the end towards the 0th index, we get the first instance of a non-infinity element whose position is the length of our required LIS.
This approach’s main point is that ith index means the counter is i, and the last element of our increasing subsequence is present at ith index.
C++ implementation of the approach
//DP approach for Longest Increasing Subsequence problem // O(n log n) solution
int maxLength = 0; for(int i=size; i>=0; i--){ if(dp[i] != INT32_MAX){ maxLength = i; break; } } cout << "The length of the Longest Increasing Subsequence is: " << maxLength << endl; }
int main(){
int input[] = {10, 5, 8, 3, 9, 4, 12, 11}; //input array int size = sizeof(input) / sizeof(input[0]); //size of input array LIS_length(input, size); return0; }
Output
The code displays the length of the longest increasing subsequence present in the input array. The output generated is:
The length of the Longest Increasing Subsequence is: 4
Complexities
Time Complexity
We iterate once through the entire input array in this approach, which takes O(n) time. We use the upper_bound() function inside the for loop, which uses O(log n) time. Thus overall time complexity is,
T(n) = O(n log n),
where n is the size of the input array.
Space Complexity
In this approach, we create a 1D dp array of size (n+1), which serves as the counter/size indicator of our LIS. Thus,
What does the standard template function (stf) upper_bound() return? Irrespective of the fact that whether the element is present in the search array or not, the upper_bound() function returns the alias of the next higher value present in the array. So, to get that value, we subtract the base address of the array that, in turn, gives us the index of the next higher value.
What are different ways to solve the problem- longest increasing subsequence? The problem can be solved using two different techniques: 1. Recursion has time complexity O(2^n). 2. Dynamic Programming has time complexity O(n^2) and O(nlogn).
This article discusses the dynamic programming approach of the Longest Increasing Subsequence having O(n log n) time complexity. We first saw the problem statement, then explained the approach used, and finally, the solution code in C++.
84+ registered