Longest Increasing Subsequence (LIS)
Given an array arr[] of size N, the task is to find the length of the Longest Increasing Subsequence (LIS) i.e., the longest possible subsequence in which the elements of the subsequence are sorted in increasing order.
Longest Increasing Subsequence
Examples:
Input: arr[] = {3, 10, 2, 1, 20}
Output: 3
Explanation: The longest increasing subsequence is 3, 10, 20Input: arr[] = {50, 3, 10, 7, 40, 80}
Output: 4
Explanation: The longest increasing subsequence is {3, 7, 40, 80}Input: arr[] = {30, 20, 10}
Output:1
Explanation: The longest increasing subsequences are {30}, {20} and (10)Input: arr[] = {10, 20, 35, 80}
Output: 4
Explanation: The whole array is sorted
Longest Increasing Sequence using Recursion:
The idea to do traverse the input array from left to right and find length of the Longest Increasing Subsequence (LIS) ending with every element arr[i]. Let the length found for arr[i] be L[i]. At the end we return maximum of all L[i] values. Now the question arises, how do we compute L[i]? For this, we us recursion, we consider all smaller elements on left of arr[i], recursively compute LIS value for all the smaller elements on left, take the maximum of all and add 1 to it. If there is no smaller element on left of an element, we return 1.
Let L(i) be the length of the LIS ending at index i such that arr[i] is the last element of the LIS. Then, L(i) can be recursively written as:
- L(i) = 1 + max(L(j) ) where 0 < j < i and arr[j] < arr[i]; or
- L(i) = 1, if no such j exists.
Formally, the length of LIS ending at index i, is 1 greater than the maximum of lengths of all LIS ending at some index j such that arr[j] < arr[i] where j < i.
We can see that the above recurrence relation follows the optimal substructure property.
Illustration:
Follow the below illustration for a better understanding:
Consider arr[] = {3, 10, 2, 11}
L(i): Denotes LIS of subarray ending at position ‘i’
Recursion Tree
Follow the steps mentioned below to implement the above idea:
- Create a recursive function.
- For each recursive call, Iterate from the i = 1 to the current position and do the following:
- Find the possible length of the longest increasing subsequence ending at the current position if the previous sequence ended at i.
- Update the maximum possible length accordingly.
- Repeat this for all indices and find the answer
Below is the implementation of the recursive approach:
// A Naive C++ recursive implementation
// of LIS problem
#include <bits/stdc++.h>
using namespace std;
// To make use of recursive calls, this
// function must return two things:
// 1) Length of LIS ending with element
// arr[n-1].
// We use max_ending_here for this purpose
// 2) Overall maximum as the LIS may end
// with an element before arr[n-1] max_ref
// is used this purpose.
// The value of LIS of full array of size
// n is stored in *max_ref which is
// our final result
int _lis(int arr[], int n, int* max_ref)
{
// Base case
if (n == 1)
return 1;
// 'max_ending_here' is length of
// LIS ending with arr[n-1]
int res, max_ending_here = 1;
// Recursively get all LIS ending with
// arr[0], arr[1] ... arr[n-2]. If
// arr[i-1] is smaller than arr[n-1],
// and max ending with arr[n-1] needs
// to be updated, then update it
for (int i = 1; i < n; i++) {
res = _lis(arr, i, max_ref);
if (arr[i - 1] < arr[n - 1]
&& res + 1 > max_ending_here)
max_ending_here = res + 1;
}
// Compare max_ending_here with the
// overall max. And update the
// overall max if needed
if (*max_ref < max_ending_here)
*max_ref = max_ending_here;
// Return length of LIS ending
// with arr[n-1]
return max_ending_here;
}
// The wrapper function for _lis()
int lis(int arr[], int n)
{
// The max variable holds the result
int max = 1;
// The function _lis() stores its
// result in max
_lis(arr, n, &max);
// Returns max
return max;
}
// Driver program to test above function
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << "Length of lis is " << lis(arr, n);
return 0;
}
// A Naive C recursive implementation
// of LIS problem
#include <stdio.h>
#include <stdlib.h>
// To make use of recursive calls, this
// function must return two things:
// 1) Length of LIS ending with element arr[n-1].
// We use max_ending_here for this purpose
// 2) Overall maximum as the LIS may end with
// an element before arr[n-1] max_ref is
// used this purpose.
// The value of LIS of full array of size n
// is stored in *max_ref which is our final result
int _lis(int arr[], int n, int* max_ref)
{
// Base case
if (n == 1)
return 1;
// 'max_ending_here' is length of LIS
// ending with arr[n-1]
int res, max_ending_here = 1;
// Recursively get all LIS ending with arr[0],
// arr[1] ... arr[n-2]. If arr[i-1] is smaller
// than arr[n-1], and max ending with arr[n-1]
// needs to be updated, then update it
for (int i = 1; i < n; i++) {
res = _lis(arr, i, max_ref);
if (arr[i - 1] < arr[n - 1]
&& res + 1 > max_ending_here)
max_ending_here = res + 1;
}
// Compare max_ending_here with the overall
// max. And update the overall max if needed
if (*max_ref < max_ending_here)
*max_ref = max_ending_here;
// Return length of LIS ending with arr[n-1]
return max_ending_here;
}
// The wrapper function for _lis()
int lis(int arr[], int n)
{
// The max variable holds the result
int max = 1;
// The function _lis() stores its result in max
_lis(arr, n, &max);
// returns max
return max;
}
// Driver program to test above function
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
printf("Length of lis is %d", lis(arr, n));
return 0;
}
// A Naive Java Program for LIS Implementation
import java.io.*;
import java.util.*;
class LIS {
// Stores the LIS
static int max_ref;
// To make use of recursive calls, this function must
// return two things: 1) Length of LIS ending with
// element arr[n-1]. We use max_ending_here for this
// purpose 2) Overall maximum as the LIS may end with an
// element before arr[n-1] max_ref is used this purpose.
// The value of LIS of full array of size n is stored in
// *max_ref which is our final result
static int _lis(int arr[], int n)
{
// Base case
if (n == 1)
return 1;
// 'max_ending_here' is length of LIS ending with
// arr[n-1]
int res, max_ending_here = 1;
// Recursively get all LIS ending with arr[0],
// arr[1] ... arr[n-2]. If arr[i-1] is smaller
// than arr[n-1], and max ending with arr[n-1] needs
// to be updated, then update it
for (int i = 1; i < n; i++) {
res = _lis(arr, i);
if (arr[i - 1] < arr[n - 1]
&& res + 1 > max_ending_here)
max_ending_here = res + 1;
}
// Compare max_ending_here with the overall max. And
// update the overall max if needed
if (max_ref < max_ending_here)
max_ref = max_ending_here;
// Return length of LIS ending with arr[n-1]
return max_ending_here;
}
// The wrapper function for _lis()
static int lis(int arr[], int n)
{
// The max variable holds the result
max_ref = 1;
// The function _lis() stores its result in max
_lis(arr, n);
// Returns max
return max_ref;
}
// Driver program to test above functions
public static void main(String args[])
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = arr.length;
// Function call
System.out.println("Length of lis is "
+ lis(arr, n));
}
}
// This code is contributed by Rajat Mishra
# A naive Python implementation of LIS problem
# Global variable to store the maximum
global maximum
# To make use of recursive calls, this function must return
# two things:
# 1) Length of LIS ending with element arr[n-1]. We use
# max_ending_here for this purpose
# 2) Overall maximum as the LIS may end with an element
# before arr[n-1] max_ref is used this purpose.
# The value of LIS of full array of size n is stored in
# *max_ref which is our final result
def _lis(arr, n):
# To allow the access of global variable
global maximum
# Base Case
if n == 1:
return 1
# maxEndingHere is the length of LIS ending with arr[n-1]
maxEndingHere = 1
# Recursively get all LIS ending with
# arr[0], arr[1]..arr[n-2]
# If arr[i-1] is smaller than arr[n-1], and
# max ending with arr[n-1] needs to be updated,
# then update it
for i in range(1, n):
res = _lis(arr, i)
if arr[i-1] < arr[n-1] and res+1 > maxEndingHere:
maxEndingHere = res + 1
# Compare maxEndingHere with overall maximum. And
# update the overall maximum if needed
maximum = max(maximum, maxEndingHere)
return maxEndingHere
def lis(arr):
# To allow the access of global variable
global maximum
# Length of arr
n = len(arr)
# Maximum variable holds the result
maximum = 1
# The function _lis() stores its result in maximum
_lis(arr, n)
return maximum
# Driver program to test the above function
if __name__ == '__main__':
arr = [10, 22, 9, 33, 21, 50, 41, 60]
n = len(arr)
# Function call
print("Length of lis is", lis(arr))
# This code is contributed by NIKHIL KUMAR SINGH
using System;
// A Naive C# Program for LIS Implementation
class LIS {
// Stores the LIS
static int max_ref;
// To make use of recursive calls, this function must
// return two things: 1) Length of LIS ending with
// element arr[n-1]. We use max_ending_here for this
// purpose 2) Overall maximum as the LIS may end with an
// element before arr[n-1] max_ref is used this purpose.
// The value of LIS of full array of size n is stored in
// *max_ref which is our final result
static int _lis(int[] arr, int n)
{
// Base case
if (n == 1)
return 1;
// 'max_ending_here' is length of LIS ending with
// arr[n-1]
int res, max_ending_here = 1;
// Recursively get all LIS ending with arr[0],
// arr[1] ... arr[n-2]. If arr[i-1] is smaller
// than arr[n-1], and max ending with arr[n-1] needs
// to be updated, then update it
for (int i = 1; i < n; i++) {
res = _lis(arr, i);
if (arr[i - 1] < arr[n - 1]
&& res + 1 > max_ending_here)
max_ending_here = res + 1;
}
// Compare max_ending_here with the overall max
// and update the overall max if needed
if (max_ref < max_ending_here)
max_ref = max_ending_here;
// Return length of LIS ending with arr[n-1]
return max_ending_here;
}
// The wrapper function for _lis()
static int lis(int[] arr, int n)
{
// The max variable holds the result
max_ref = 1;
// The function _lis() stores its result in max
_lis(arr, n);
// Returns max
return max_ref;
}
// Driver program to test above functions
public static void Main()
{
int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = arr.Length;
// Function call
Console.Write("Length of lis is " + lis(arr, n)
+ "\n");
}
}
<script>
/* A Naive javascript Program for LIS Implementation */
let max_ref; // stores the LIS
/* To make use of recursive calls, this function must return
two things:
1) Length of LIS ending with element arr[n-1]. We use
max_ending_here for this purpose
2) Overall maximum as the LIS may end with an element
before arr[n-1] max_ref is used this purpose.
The value of LIS of full array of size n is stored in
*max_ref which is our final result */
function _lis(arr,n)
{
// base case
if (n == 1)
return 1;
// 'max_ending_here' is length of LIS ending with arr[n-1]
let res, max_ending_here = 1;
/* Recursively get all LIS ending with arr[0], arr[1] ...
arr[n-2]. If arr[i-1] is smaller than arr[n-1], and
max ending with arr[n-1] needs to be updated, then
update it */
for (let i = 1; i < n; i++)
{
res = _lis(arr, i);
if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)
max_ending_here = res + 1;
}
// Compare max_ending_here with the overall max. And
// update the overall max if needed
if (max_ref < max_ending_here)
max_ref = max_ending_here;
// Return length of LIS ending with arr[n-1]
return max_ending_here;
}
// The wrapper function for _lis()
function lis(arr,n)
{
// The max variable holds the result
max_ref = 1;
// The function _lis() stores its result in max
_lis( arr, n);
// returns max
return max_ref;
}
// driver program to test above functions
let arr=[10, 22, 9, 33, 21, 50, 41, 60 ]
let n = arr.length;
document.write("Length of lis is "
+ lis(arr, n) + "<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Output
Length of lis is 5
Time Complexity: O(2n) The time complexity of this recursive approach is exponential as there is a case of overlapping subproblems as explained in the recursive tree diagram above.
Auxiliary Space: O(1). No external space is used for storing values apart from the internal stack space.
Longest Increasing Subsequence using Memoization:
If noticed carefully, we can see that the above recursive solution also follows the overlapping subproblems property i.e., same substructure solved again and again in different recursion call paths. We can avoid this using the memoization approach.
We can see that each state can be uniquely identified using two parameters:
- Current index (denotes the last index of the LIS) and
- Previous index (denotes the ending index of the previous LIS behind which the arr[i] is being concatenated).
Below is the implementation of the above approach.
// C++ code of memoization approach for LIS
#include <bits/stdc++.h>
using namespace std;
// To make use of recursive calls, this
// function must return two things:
// 1) Length of LIS ending with element
// arr[n-1].
// We use max_ending_here for this purpose
// Overall maximum as the LIS may end with
// an element before arr[n-1] max_ref is
// used this purpose.
// The value of LIS of full array of size
// n is stored in *max_ref which is
// our final result
int f(int idx, int prev_idx, int n, int a[],
vector<vector<int> >& dp)
{
if (idx == n) {
return 0;
}
if (dp[idx][prev_idx + 1] != -1) {
return dp[idx][prev_idx + 1];
}
int notTake = 0 + f(idx + 1, prev_idx, n, a, dp);
int take = INT_MIN;
if (prev_idx == -1 || a[idx] > a[prev_idx]) {
take = 1 + f(idx + 1, idx, n, a, dp);
}
return dp[idx][prev_idx + 1] = max(take, notTake);
}
// Function to find length of
// longest increasing subsequence
int longestSubsequence(int n, int a[])
{
vector<vector<int> > dp(n + 1, vector<int>(n + 1, -1));
return f(0, -1, n, a, dp);
}
// Driver program to test above function
int main()
{
int a[] = { 3, 10, 2, 1, 20 };
int n = sizeof(a) / sizeof(a[0]);
// Function call
cout << "Length of lis is " << longestSubsequence(n, a);
return 0;
}
// A Memoization Java Program for LIS Implementation
import java.lang.*;
import java.util.Arrays;
class LIS {
// To make use of recursive calls, this function must
// return two things: 1) Length of LIS ending with
// element arr[n-1]. We use max_ending_here for this
// purpose 2) Overall maximum as the LIS may end with an
// element before arr[n-1] max_ref is used this purpose.
// The value of LIS of full array of size n is stored in
// *max_ref which is our final result
static int f(int idx, int prev_idx, int n, int a[],
int[][] dp)
{
if (idx == n) {
return 0;
}
if (dp[idx][prev_idx + 1] != -1) {
return dp[idx][prev_idx + 1];
}
int notTake = 0 + f(idx + 1, prev_idx, n, a, dp);
int take = Integer.MIN_VALUE;
if (prev_idx == -1 || a[idx] > a[prev_idx]) {
take = 1 + f(idx + 1, idx, n, a, dp);
}
return dp[idx][prev_idx + 1]
= Math.max(take, notTake);
}
// The wrapper function for _lis()
static int lis(int arr[], int n)
{
// The function _lis() stores its result in max
int dp[][] = new int[n + 1][n + 1];
for (int row[] : dp)
Arrays.fill(row, -1);
return f(0, -1, n, arr, dp);
}
// Driver program to test above functions
public static void main(String args[])
{
int a[] = { 3, 10, 2, 1, 20 };
int n = a.length;
// Function call
System.out.println("Length of lis is " + lis(a, n));
}
}
// This code is contributed by Sanskar.
# A Naive Python recursive implementation
# of LIS problem
import sys
# To make use of recursive calls, this
# function must return two things:
# 1) Length of LIS ending with element arr[n-1].
# We use max_ending_here for this purpose
# 2) Overall maximum as the LIS may end with
# an element before arr[n-1] max_ref is
# used this purpose.
# The value of LIS of full array of size n
# is stored in *max_ref which is our final result
def f(idx, prev_idx, n, a, dp):
if (idx == n):
return 0
if (dp[idx][prev_idx + 1] != -1):
return dp[idx][prev_idx + 1]
notTake = 0 + f(idx + 1, prev_idx, n, a, dp)
take = -sys.maxsize - 1
if (prev_idx == -1 or a[idx] > a[prev_idx]):
take = 1 + f(idx + 1, idx, n, a, dp)
dp[idx][prev_idx + 1] = max(take, notTake)
return dp[idx][prev_idx + 1]
# Function to find length of longest increasing
# subsequence.
def longestSubsequence(n, a):
dp = [[-1 for i in range(n + 1)]for j in range(n + 1)]
return f(0, -1, n, a, dp)
# Driver program to test above function
if __name__ == '__main__':
a = [3, 10, 2, 1, 20]
n = len(a)
# Function call
print("Length of lis is", longestSubsequence(n, a))
# This code is contributed by shinjanpatra
// C# approach to implementation the memoization approach
using System;
class GFG {
// To make use of recursive calls, this
// function must return two things:
// 1) Length of LIS ending with element arr[n-1].
// We use max_ending_here for this purpose
// 2) Overall maximum as the LIS may end with
// an element before arr[n-1] max_ref is
// used this purpose.
// The value of LIS of full array of size n
// is stored in *max_ref which is our final result
public static int INT_MIN = -2147483648;
public static int f(int idx, int prev_idx, int n,
int[] a, int[, ] dp)
{
if (idx == n) {
return 0;
}
if (dp[idx, prev_idx + 1] != -1) {
return dp[idx, prev_idx + 1];
}
int notTake = 0 + f(idx + 1, prev_idx, n, a, dp);
int take = INT_MIN;
if (prev_idx == -1 || a[idx] > a[prev_idx]) {
take = 1 + f(idx + 1, idx, n, a, dp);
}
return dp[idx, prev_idx + 1]
= Math.Max(take, notTake);
}
// Function to find length of longest increasing
// subsequence.
public static int longestSubsequence(int n, int[] a)
{
int[, ] dp = new int[n + 1, n + 1];
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < n + 1; j++) {
dp[i, j] = -1;
}
}
return f(0, -1, n, a, dp);
}
// Driver code
static void Main()
{
int[] a = { 3, 10, 2, 1, 20 };
int n = a.Length;
Console.WriteLine("Length of lis is "
+ longestSubsequence(n, a));
}
}
// The code is contributed by Nidhi goel.
/* A Naive Javascript recursive implementation
of LIS problem */
/* To make use of recursive calls, this
function must return two things:
1) Length of LIS ending with element arr[n-1].
We use max_ending_here for this purpose
2) Overall maximum as the LIS may end with
an element before arr[n-1] max_ref is
used this purpose.
The value of LIS of full array of size n
is stored in *max_ref which is our final result
*/
function f(idx, prev_idx, n, a, dp) {
if (idx == n) {
return 0;
}
if (dp[idx][prev_idx + 1] != -1) {
return dp[idx][prev_idx + 1];
}
var notTake = 0 + f(idx + 1, prev_idx, n, a, dp);
var take = Number.MIN_VALUE;
if (prev_idx == -1 || a[idx] > a[prev_idx]) {
take = 1 + f(idx + 1, idx, n, a, dp);
}
return (dp[idx][prev_idx + 1] = Math.max(take, notTake));
}
// Function to find length of longest increasing
// subsequence.
function longestSubsequence(n, a) {
var dp = Array(n + 1)
.fill()
.map(() => Array(n + 1).fill(-1));
return f(0, -1, n, a, dp);
}
/* Driver program to test above function */
var a = [3, 10, 2, 1, 20];
var n = 5;
console.log("Length of lis is " + longestSubsequence(n, a));
// This code is contributed by satwiksuman.
Output
Length of lis is 3
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Longest Increasing Subsequence using Dynamic Programming:
Due to optimal substructure and overlapping subproblem property, we can also utilise Dynamic programming to solve the problem. Instead of memoization, we can use the nested loop to implement the recursive relation.
The outer loop will run from i = 1 to N and the inner loop will run from j = 0 to i and use the recurrence relation to solve the problem.
Below is the implementation of the above approach:
// Dynamic Programming C++ implementation
// of LIS problem
#include <bits/stdc++.h>
using namespace std;
// lis() returns the length of the longest
// increasing subsequence in arr[] of size n
int lis(int arr[], int n)
{
int lis[n];
lis[0] = 1;
// Compute optimized LIS values in
// bottom up manner
for (int i = 1; i < n; i++) {
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 maximum value in lis[]
return *max_element(lis, lis + n);
}
// Driver program to test above function
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
printf("Length of lis is %d\n", lis(arr, n));
return 0;
}
// Dynamic Programming Java implementation
// of LIS problem
import java.lang.*;
class LIS {
// lis() returns the length of the longest
// increasing subsequence in arr[] of size n
static int lis(int arr[], int n)
{
int lis[] = new int[n];
int i, j, max = 0;
// Initialize LIS values for all indexes
for (i = 0; i < n; i++)
lis[i] = 1;
// Compute optimized LIS values in
// bottom up manner
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;
// Pick maximum of all LIS values
for (i = 0; i < n; i++)
if (max < lis[i])
max = lis[i];
return max;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = arr.length;
// Function call
System.out.println("Length of lis is "
+ lis(arr, n));
}
}
// This code is contributed by Rajat Mishra
# Dynamic programming Python implementation
# of LIS problem
# lis returns length of the longest
# increasing subsequence in arr of size n
def lis(arr):
n = len(arr)
# Declare the list (array) for LIS and
# initialize LIS values for all indexes
lis = [1]*n
# Compute optimized LIS values in bottom up manner
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
# Initialize maximum to 0 to get
# the maximum of all LIS
maximum = 0
# Pick maximum of all LIS values
for i in range(n):
maximum = max(maximum, lis[i])
return maximum
# Driver program to test above function
if __name__ == '__main__':
arr = [10, 22, 9, 33, 21, 50, 41, 60]
print("Length of lis is", lis(arr))
# This code is contributed by Nikhil Kumar Singh
// Dynamic Programming C# implementation of LIS problem
using System;
class LIS {
// lis() returns the length of the longest increasing
// subsequence in arr[] of size n
static int lis(int[] arr, int n)
{
int[] lis = new int[n];
int i, j, max = 0;
// Initialize LIS values for all indexes
for (i = 0; i < n; i++)
lis[i] = 1;
// Compute optimized LIS values in bottom up manner
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;
// Pick maximum of all LIS values
for (i = 0; i < n; i++)
if (max < lis[i])
max = lis[i];
return max;
}
// Driver code
public static void Main()
{
int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = arr.Length;
// Function call
Console.WriteLine("Length of lis is "
+ lis(arr, n));
}
}
// This code is contributed by Ryuga
<script>
// Dynamic Programming Javascript implementation
// of LIS problem
// lis() returns the length of the longest
// increasing subsequence in arr[] of size n
function lis(arr, n)
{
let lis = Array(n).fill(0);
let i, j, max = 0;
// Initialize LIS values for all indexes
for(i = 0; i < n; i++)
lis[i] = 1;
// Compute optimized LIS values in
// bottom up manner
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;
// Pick maximum of all LIS values
for(i = 0; i < n; i++)
if (max < lis[i])
max = lis[i];
return max;
}
// Driver code
let arr = [ 10, 22, 9, 33, 21, 50, 41, 60 ];
let n = arr.length;
document.write("Length of lis is " + lis(arr, n) + "\n");
// This code is contributed by avijitmondal1998
</script>
Output
Length of lis is 5
Time Complexity: O(N2) As a nested loop is used.
Auxiliary Space: O(N) Use of any array to store LIS values at each index.
Note: The time complexity of the above Dynamic Programming (DP) solution is O(n^2), but there is an O(N* logN) solution for the LIS problem. We have not discussed the O(N log N) solution here.
Refer: Longest Increasing Subsequence Size (N * logN) for the mentioned approach.
Contact Us