Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach and Explanation
3.1.
C++ implementation of the approach
3.2.
Complexities
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Frequently Asked Questions
5.
Key Takeaways
Last Updated: Mar 27, 2024

Longest Increasing Subsequence | Part 2

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

You can learn more about the upper_bound() function by reading this article: Exploring the STL libraries in C++

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.

Also Read, Byte Array to String

Problem Statement

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}.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

#include <bits/stdc++.h>
using namespace std;

void LIS_length(int input[], int size){

    int dp[size+1];

    for(int i=1; i<=size; i++){
        dp[i] = INT32_MAX;
    }
    dp[0] = INT32_MIN;

    for(int i=0; i<size; i++){
        int idx = upper_bound(dp, dp+size+1, input[i]) - dp;
        if(dp[idx-1] < input[i] && dp[idx] > input[i]){
            dp[idx] = input[i];
        }
    }

    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[] = {10583941211};  //input array
    int size = sizeof(input) / sizeof(input[0]);   //size of input array
 
    LIS_length(input, size);
    return 0;
}

 

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, 

Space Complexity = O(n+1),

where n is the size of the input array.

Check out this : Longest common subsequence

Frequently Asked Questions

  1. 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. 
     
  2. 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).
     
  3. What are some other problems including subsequences?
    Try the problems- Longest Common SubsequenceLongest Consecutive Subsequence on Coding Ninjas Studio.

Key Takeaways

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++.

Want to learn more about Dynamic Programming? Try solving the following problem : Longest Palindromic Subsequence. 

Want to solve coding problems asked in various IT companies? Practice such questions on our Coding Ninjas Studio - The best platform to prepare for coding interviews 

 

Live masterclass