Longest Increasing Subsequence

Published by

youngkih21

on

October 4, 2020

Longest Increasing Subsequence(LIS) is one of the most common problems of dynamic programming.

Longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible

For example, when we have a sequence of numbers as below,

10

20

10

30

20

50

the longest increasing subsequence is [10, 20, 30, 50] as pointed in red color.

10

20

10

30

20

50

There are couple ways to get the sequence of numbers, each of them with different time complexity.

Solution #1 – ⭐️⭐️⭐️

Time Complexity : O(N^2)

Suppose we have an array dp[n] that contain values of LIS from the start index(0) to current index(n-1).
If that so, the initial dp[n] will have 1 in each index.

1

Then, iterate from index 0 to n-1, updating the values comparing with the ones in front.

Algorithm

When 0 <= j < n,
if ( arr[j] < arr[n] ) , dp[n] = Max( dp[n], dp[j] + 1 )

For example,
n = 0)

arr[]	10	20	10	30	20	50
dp[]	1	1	1	1	1	1

n = 1)
As arr[0] < arr[1], dp[1] = Max(dp[1], dp[0] + 1) = Max(1, 2) = 2

arr[]	10	20	10	30	20	50
dp[]	1	2	1	1	1	1

n = 2)
As arr[0] == arr[2], do nothing.

arr[]	10	20	10	30	20	50
dp[]	1	2	1	1	1	1

As arr[1] > arr[2], do nothing.

arr[]	10	20	10	30	20	50
dp[]	1	2	1	1	1	1

n = 3)
As arr[0] < arr[3], dp[3] = Max(dp[3], dp[0] + 1) = Max(1, 2) = 2

arr[]	10	20	10	30	20	50
dp[]	1	2	1	2	1	1

As arr[1] < arr[3], dp[3] = Max(dp[3], dp[1] + 1) = Max(2, 3) = 3

arr[]	10	20	10	30	20	50
dp[]	1	2	1	3	1	1

As arr[2] < arr[3], dp[3] = Max(dp[3], dp[1] + 1) = Max(3, 2) = 3

arr[]	10	20	10	30	20	50
dp[]	1	2	1	3	1	1

n = 4)
As arr[0] < arr[4], dp[4] = Max(dp[4], dp[0] + 1) = Max(1, 2) = 2

arr[]	10	20	10	30	20	50
dp[]	1	2	1	3	2	1

As arr[1] == arr[4], do nothing.

arr[]	10	20	10	30	20	50
dp[]	1	2	1	3	2	1

As arr[2] < arr[4], dp[4] = Max(dp[4], dp[2] + 1) = Max(2, 2) = 2

arr[]	10	20	10	30	20	50
dp[]	1	2	1	3	2	1

As arr[3] > arr[4], do nothing.

arr[]	10	20	10	30	20	50
dp[]	1	2	1	3	2	1

n = 5)
As arr[0] < arr[5], dp[5] = Max(dp[5], dp[0] + 1) = Max(1, 2) = 2

arr[]	10	20	10	30	20	50
dp[]	1	2	1	3	2	2

As arr[1] < arr[5], dp[5] = Max(dp[5], dp[1] + 1) = Max(2, 3) = 3

arr[]	10	20	10	30	20	50
dp[]	1	2	1	3	2	3

As arr[2] < arr[5], dp[5] = Max(dp[5], dp[2] + 1) = Max(3, 2) = 3

arr[]	10	20	10	30	20	50
dp[]	1	2	1	3	2	3

As arr[3] < arr[5], dp[5] = Max(dp[5], dp[3] + 1) = Max(3, 4) = 4

arr[]	10	20	10	30	20	50
dp[]	1	2	1	3	2	4

As arr[4] < arr[5], dp[5] = Max(dp[5], dp[4] + 1) = Max(4, 3) = 4

arr[]	10	20	10	30	20	50
dp[]	1	2	1	3	2	4

As the dp[n-1] might not be the maximum value, to get the length of LIS, iterate through dp[] array.

To get the array LIS sequence itself, start from the index whose value is max and iterate to left for the next item that is (value-1). For example,

arr[]	10	20	10	30	20	50
dp[]	1	2	1	3	2	4

As dp[5] = 4, dp[4] = 3, dp[1] = 2, dp[0] = 1, LIS sequence is the according number, {10, 20, 30, 50}.

Solution #2 – ⭐️⭐️⭐️⭐️⭐️

Time Complexity : O(NLogN)

This solution is based on the idea of creating a new array in increasing order, but with numbers overriding the lower bound number.
From this solution, it is easier to regard each element in the new array as ‘pile‘ of cards just like the card games like below.

Algorithm

Create a new array(or arraylist), arr2[]
Iterate through arr[] and put it in arr2[] in ascending order.
1. If arr[i] is bigger than every number in arr2[], add it to the last index.
2. If not, replace arr[i] with the lower bound number in arr2[].
  1. Lower bound number : “A lower bound or minorant of S is defined to be an element of K which is less than or equal to every element of S”
  2. To find the lower bound number, use Binary Search.

For example, the arr2[] will be updated as below.

arr[]	10	20	10	30	20	50
arr2[]

arr[]	10	20	10	30	20	50
arr2[]	10

arr[]	10	20	10	30	20	50
arr2[]	10	20

arr[]	10	20	10	30	20	50
arr2[]	10	20

arr[]	10	20	10	30	20	50
arr2[]	10	20	30

arr[]	10	20	10	30	20	50
arr2[]	10	20	30

arr[]	10	20	10	30	20	50
arr2[]	10	20	30	50

The length of arr2[] array is the length of LIS array.

However, note that the arr2[] itself it NOT the LIS array as we have been replacing the arr2[] with lower bound numbers.
To retrieve the LIS array itself, we need to create a separate array( pileArr[] ) that would contain the information of each arr[] number’s index in arr2[]. From the case above, it would be like below, as
arr[0] is in arr2[0],
arr[1] in arr2[1],
arr[2] in arr2[0],
arr[3] in arr2[2], …

pileArr[]

0

1

0

2

1

3

And then to get the LIS array, just as Solution #1, start from the max number of pileArr[] and iterate to left, and get the according index’s number from arr[].

pileArr[]

0

1

0

2

1

3

Will the Guru