2010-04-13 17:26:50 8 Comments

I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming.

### Related Questions

#### Sponsored Content

#### 10 Answered Questions

### [SOLVED] What is dynamic programming?

**2009-06-30 19:10:24****unknown****132717**View**265**Score**10**Answer- Tags: algorithm dynamic-programming

#### 44 Answered Questions

#### 38 Answered Questions

### [SOLVED] Find an integer not among four billion given ones

**2011-08-22 21:11:47****SecureFish****112772**View**681**Score**38**Answer- Tags: algorithm file search out-of-memory memory-limit

#### 11 Answered Questions

### [SOLVED] Dynamic programming: Find longest subsequence that is zig zag

**2011-08-02 16:01:11****Abhijeet Kashnia****25284**View**16**Score**11**Answer- Tags: algorithm dynamic-programming

#### 2 Answered Questions

### [SOLVED] Constrained Longest Increasing Subsequence

**2018-05-22 16:27:32****Raghav****141**View**2**Score**2**Answer- Tags: algorithm dynamic-programming computer-science memoization lis

#### 1 Answered Questions

### [SOLVED] Longest Increasing Subsequence, Dynamic Programing

**2016-12-11 20:36:13****Jerome Ansia****390**View**0**Score**1**Answer- Tags: java algorithm dynamic-programming

#### 1 Answered Questions

### [SOLVED] How to determine the longest increasing sub-sequence using dynamic programming with joinable input integers

**2016-04-25 20:37:58****iman****108**View**1**Score**1**Answer- Tags: algorithm computer-science dynamic-programming lis

#### 1 Answered Questions

### [SOLVED] Reducing Longest common subsequence to Longest increasing Subsequence

**2016-01-07 13:11:17****user3087202****1155**View**1**Score**1**Answer- Tags: algorithm dynamic-programming

## 16 comments

## @Ashish kumar 2019-07-17 18:31:53

Simplest LIS solution in C++ with O(nlog(n)) time complexityOUTPUT:

4

## @Abhinav Vajpeyi 2019-06-27 13:03:15

Here is my Leetcode solution using Binary Search:->

## @ravi tanwar 2018-07-06 15:16:50

even though there is a way by which you can solve this in O(nlogn) time(this solves in O(n^2) time) but still this way gives the dynamic programming approach which is also good .

## @Mostafizar 2017-02-17 20:27:54

O(n^2) java implementation:

## @Salvador Dali 2016-04-25 09:33:45

Speaking about DP solution, I found it surprising that no one mentioned the fact that LIS can be reduced to LCS. All you need to do is sort the copy of the original sequence, remove all the duplicates and do LCS of them. In pseudocode it is:

And the full implementation written in Go. You do not need to maintain the whole n^2 DP matrix if you do not need to reconstruct the solution.

## @max 2017-06-28 18:06:33

That would be O(N^2) solution, right?

## @Salvador Dali 2017-06-28 18:16:23

@max yes, it is kind of written in the answer with LCS, n^2 matrix

## @Petar Minchev 2010-04-13 17:39:57

OK, I will describe first the simplest solution which is O(N^2), where N is the size of the collection. There also exists a O(N log N) solution, which I will describe also. Look here for it at the section Efficient algorithms.

I will assume the indices of the array are from 0 to N - 1. So let's define

`DP[i]`

to be the length of the LIS (Longest increasing subsequence) which is ending at element with index`i`

. To compute`DP[i]`

we look at all indices`j < i`

and check both if`DP[j] + 1 > DP[i]`

and`array[j] < array[i]`

(we want it to be increasing). If this is true we can update the current optimum for`DP[i]`

. To find the global optimum for the array you can take the maximum value from`DP[0...N - 1]`

.I use the array

`prev`

to be able later to find the actual sequence not only its length. Just go back recursively from`bestEnd`

in a loop using`prev[bestEnd]`

. The`-1`

value is a sign to stop.## OK, now to the more efficient

`O(N log N)`

solution:Let

`S[pos]`

be defined as the smallest integer that ends an increasing sequence of length`pos`

. Now iterate through every integer`X`

of the input set and do the following:If

`X`

> last element in`S`

, then append`X`

to the end of`S`

. This essentialy means we have found a new largest`LIS`

.Otherwise find the smallest element in

`S`

, which is`>=`

than`X`

, and change it to`X`

. Because`S`

is sorted at any time, the element can be found using binary search in`log(N)`

.Total runtime -

`N`

integers and a binary search for each of them - N * log(N) = O(N log N)Now let's do a real example:

Collection of integers:

`2 6 3 4 1 2 9 5 8`

Steps:

So the length of the LIS is

`5`

(the size of S).To reconstruct the actual

`LIS`

we will again use a parent array. Let`parent[i]`

be the predecessor of element with index`i`

in the`LIS`

ending at element with index`i`

.To make things simpler, we can keep in the array

`S`

, not the actual integers, but their indices(positions) in the set. We do not keep`{1, 2, 4, 5, 8}`

, but keep`{4, 5, 3, 7, 8}`

.That is input[4] =

1, input[5] =2, input[3] =4, input[7] =5, input[8] =8.If we update properly the parent array, the actual LIS is:

Now to the important thing - how do we update the parent array? There are two options:

If

`X`

> last element in`S`

, then`parent[indexX] = indexLastElement`

. This means the parent of the newest element is the last element. We just prepend`X`

to the end of`S`

.Otherwise find the index of the smallest element in

`S`

, which is`>=`

than`X`

, and change it to`X`

. Here`parent[indexX] = S[index - 1]`

.## @SexyBeast 2012-11-02 07:52:47

The condition should be

`if (DP[j] + 1 >= DP[i] && array[j] < array[i])`

instead of`if (DP[j] + 1 > DP[i] && array[j] < array[i])`

, don't you think so?## @Petar Minchev 2012-11-02 09:10:49

It doesn't matter. If

`DP[j] + 1 == DP[i]`

then`DP[i]`

won't become better with`DP[i] = DP[j] + 1`

. We are trying to optimize`DP[i]`

.## @SexyBeast 2012-11-21 10:52:01

Can you explain the

`O(N log N)`

solution given at the link you mentioned? I cannot understand it..## @SexyBeast 2012-11-22 05:28:22

But here the answer should be

`[1,2,5,8]`

, 4 comes before 1 in the array, how can the LIS be`[1,2,4,5,8]`

?## @Petar Minchev 2012-11-22 08:26:22

@Cupidvogel - The answer is

`[2,3,4,5,8]`

. Read carefully - the`S`

array`DOES NOT`

represent an actual sequence.`Let S[pos] be defined as the smallest integer that ends an increasing sequence of length pos.`

## @SexyBeast 2012-11-22 08:43:54

So now the length of

`S`

is 5, so I know that the length of the LIS is 5. But how do I construct the actual LIS from it, like you did in your original solution?## @Petar Minchev 2012-11-22 08:49:16

let us continue this discussion in chat

## @Petar Minchev 2012-11-22 09:13:40

I have updated my post. If you have any questions go to chat, by clicking

`continue this discussion in chat`

.## @Trying 2013-08-04 05:27:46

@PetarMinchev Nice explanation +1. Just have one doubt, can't i make this

`DP[j] + 1 > DP[i]`

to`DP[j] >= DP[i]`

? Thanks.## @Petar Minchev 2013-08-04 08:04:02

Thank you! Yes, you can make it this way.

## @hivert 2013-10-09 17:10:59

By the way, this algorithm is due to Craige Schensted.

## @Snicolas 2014-01-14 05:16:39

It seems to that the first algorithm finds the longest increasing subsequence, and the second one finds the longest increasing subset.

## @Petar Minchev 2014-01-14 07:23:14

Both algorithms find the longest increasing subsequence. What made you think the second algorithm is different?

## @Snicolas 2014-01-14 14:27:07

Position of array elements are not taken into account for "sequencing". @PetarMinchev

## @Petar Minchev 2014-01-14 15:43:38

Positions are taken into account. Please read the algorithm description at en.wikipedia.org/wiki/Longest_increasing_subsequence, in the section "Efficient algorithms".

## @Petar Minchev 2014-01-19 19:39:10

@Kraken - Yes, using the

`prev`

array you will find only one subsequence. To find all subsequences you don't need the`prev`

array. When restoring and you are at index`cur`

, then you have to examine all previous indices`i`

<`cur`

, such that`DP[i] = DP[cur] - 1`

and`array[i] < array[cur]`

. You can use recursion to print all.## @Kraken 2014-01-20 06:30:03

@PetarMinchev That will be using the first approach right? What about the second one? How do I do the entire process in nlogn?

## @Petar Minchev 2014-01-20 11:48:05

@Kraken - Well you can also do the same for the second approach. To restore all sequences, you don't need the

`parent`

array. Just create another array`DP`

, which will hold the length of`LIS`

for each position in the array. When length of`S`

is extended with one more element, then`DP[i] = length(S)`

. This was case`1`

. For case 2 -`DP[i] = positionOfSmallestElementFoundWithBinarySearch`

. After having`DP`

, then you can do the same as in my previous comment.## @Petar Minchev 2014-01-20 11:57:16

But doing effectively the process described in my previous comment is another story -

`then you have to examine all previous indices i < cur, such that DP[i] = DP[cur] - 1 and array[i] < array[cur]`

.## @Boyang 2014-04-16 12:46:12

I don't often see such clear explanations. Not only it's very easy to understand, because the doubts are cleared within the explanation, but also it addresses any implementation problem that might arise. Awesome.

## @candide 2014-05-06 10:08:23

+1 the step-by-step example. But : 1. (major) At first reading, I considered that every step in your example produces an increasing subsequence, the last step giving the requested subsequence. Indeed your comments give to understand that way (eg "New largest LIS"). Of course, this is not the case but it is easy to be confused : each step gives an increasing sequence of elements of the initial array T but NOT a SUBsequence of T; 2. (minor) a set data-structure has no natural order end no right side. However, you define the sequence to be built as a "set", eg "Initialize S to the empty set"

## @Naman 2014-05-19 11:22:28

@PetarMinchev Hi Petar, I am solving a problem of finding ALL LIS. I used second method of O(nlogn) complexity. But if I print all solution using recursion on DP structure, won't it become slower? Is there any optimized way to print all LIS?

## @Ben 2014-07-05 10:32:40

@PetarMinchev I've having some trouble understanding the parents array. Can you list how how the parent array is updated on each iteration?

## @seeker 2014-08-01 20:56:04

How does your example work? Your second algorithm with the input

`{2 6 3 4 1 2 9 5 8}`

has a LIS of`{2 3 4 5 8 }`

and NOT`{1, 2, 4, 5, 8}`

. Can you explain whats happening there?## @Petar Minchev 2014-08-02 07:43:36

S is not containing the LIS. Read again "Let S[pos] be defined as the smallest integer that could possibly end an increasing sequence of length pos". To reconstruct the LIS you need the parent array.

## @eb80 2014-08-02 20:16:21

geeksforgeeks.org/… is probably the best explanation of this i've seen

## @Ali 2014-08-26 10:16:14

@PetarMinchev Amazing explanation. Much better than geeksforgeeks.org and Wikipedia itself. Thank you so much for explaining it this brief and clearly.

## @bicepjai 2014-09-23 07:12:50

i could not understand 1) why do we have

`DP[j] + 1 > DP[i]`

this condition ? 2) how do we know that the`array[j] < array[i]`

is going to verify that there are no numbers greater than`array[j]`

before`j`

?## @Petar Minchev 2014-09-23 08:12:09

1) The condition is to make sure a smaller sequence doesn't overwrite a sequence of greater length. If

`DP[i] = 4`

, and`DP[j] + 1 = 2`

, we don't want`DP[i]`

to become`2`

and to be overwritten with a smaller length.## @Petar Minchev 2014-09-23 08:16:56

2) You seem to be confused here. There can be numbers greater than

`array[j]`

before`j`

and that is ok. The important thing is that we know that`DP[j]`

is containing the length of a sequence of only strictly increasing numbers.## @harryg 2014-11-28 11:58:27

@Peter thanks for your explanation. I'm still struggling on how to construct the LIS array having constructed

`S`

. Updating the`parent`

array doesn't seem to make sense. Do you do this in the same loop that you are finding`S`

in?## @Petar Minchev 2014-11-29 09:42:53

Yes, immediately after changing something in

`S`

, you change the`parent`

too.`S`

is containing indices.`S[pos]`

= the index of the smallest integer possible, which is the last number of a`LIS`

of length`pos`

. There are only two cases when updating`S`

and for each case you update parent accordingly. The two cases are described at the end - prepending to end of`S`

, or updating`S`

somewhere in the inside of it.## @MortalMan 2016-03-09 01:04:37

@PetarMinchev Hi, can you please explain how to find the actual LIS using the O(N log N) algorithm?

## @MortalMan 2016-03-09 01:50:54

also, how can

`S[lastElementOfS]`

exist, if S[8] doesn't exist?## @MortalMan 2016-03-09 02:22:39

You said this, about updating the parent array -

`We just prepend X to the end of S.`

Isn't that changing`S`

, not the parent array?## @Greener 2016-03-12 21:41:05

I'm having a very hard time understanding why all definitions for "DP[i]" are "the length of the LIS(Longest increasing subsequence) which is ending at element with index i". Why do we define it as such? Couldn't we define DP[i] to be the length of the longest increasing sequence that's present in the array up to index i?

## @arviman 2016-07-12 12:33:47

@Greener: because if you define DP[i] as length of LIS, then that doesn't help you build a substructure you can use to derive the higher answer order. Then, with the next value at index i+1, how do you know if it increases the LIS at any point in DP[0..i]. it just becomes like a greedy polynomial time solution.

## @arviman 2016-07-12 12:35:10

I'm having a somewhat hard time parsing this: "Let parent[i] be the predecessor of element with index i in the LIS ending at element with index i." - is it Let parent[i] be the predecessor of

element with index i in the LIS ending at element with index ior Let parent[i] be thepredecessor of element with index i in the LISending at element with index i.## @Adi agarwal 2016-12-04 18:08:56

see code here - techiedelight.com/longest-increasing-subsequence

## @Somil Bhandari 2015-11-16 17:41:52

This can be solved in O(n^2) using dynamic programming.

Process the input elements in order and maintain a list of tuples for each element. Each tuple (A,B), for the element i will denotes, A = length of longest increasing sub-sequence ending at i and B = index of predecessor of list[i] in the longest increasing sub-sequence ending at list[i].

Start from element 1, the list of tuple for element 1 will be [(1,0)] for element i, scan the list 0..i and find element list[k] such that list[k] < list[i], the value of A for element i, Ai will be Ak + 1 and Bi will be k. If there are multiple such elements, add them to the list of tuples for element i.

In the end, find all the elements with max value of A (length of LIS ending at element) and backtrack using the tuples to get the list.

I have shared the code for same at http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799

## @NathanOliver- Reinstate Monica 2015-11-16 18:19:01

You should include the code in your answer as links may break.

## @bjackfly 2013-10-28 16:10:58

The following C++ implementation includes also some code that builds the actual

longest increasing subsequenceusing an array called`prev`

.Implementation with no stack just reverse the vector

## @jayant singh 2015-10-27 11:09:16

checkout the code in java for longest increasing subsequence with the array elements

http://ideone.com/Nd2eba

## @Sam King 2013-11-09 01:48:46

Petar Minchev's explanation helped clear things up for me, but it was hard for me to parse what everything was, so I made a Python implementation with overly-descriptive variable names and lots of comments. I did a naive recursive solution, the O(n^2) solution, and the O(n log n) solution.

I hope it helps clear up the algorithms!

## The Recursive Solution

## The O(n^2) Dynamic Programming Solution

## The O(n log n) Dynamic Programming Solution

## @Johan S 2014-01-27 08:52:20

Your optimized algorithm is incorrect. Please test the case when sequence is 5, 19, 5, 81, 50, 28, 29, 1, 83, 23. Your algorithm returns 5, 19, 81, 83 when it should return 5, 19, 28, 29, 83.

## @Sam King 2014-02-24 07:01:02

Are you sure? When I run optimized_dynamic_programming_solution([5, 19, 5, 81, 50, 28, 29, 1, 83, 23]) on my computer, it returns [5, 19, 28, 29, 83].

## @mostruash 2014-06-12 09:01:28

Although I appreciate the effort here, my eyes hurt when I stare at those pseudo-codes.

## @Sam King 2014-06-12 15:39:39

mostruash -- I'm not sure what you mean. My answer doesn't have pseudo code; it has Python.

## @Adilli Adil 2015-01-04 18:16:42

Well he most probably means your naming convention of variables and functions,which also made my eyes 'hurt'

## @Sam King 2015-01-04 23:54:28

If you mean my naming convention, I'm mostly following the Google Python Style Guide. If you are advocating short variable names, I prefer descriptive variable names because they make code easier to understand and maintain.

## @ihadanny 2015-04-05 16:37:31

cool. but don't you think using

`bisect`

instead of`find_smallest_elem_as_big_as`

would clear it up?## @Sam King 2015-04-05 20:04:34

For an actual implementation, it would probably make sense to use

`bisect`

. For a demonstration of how an algorithm works and its performance characteristics, I was trying to keep things as primitive as possible.## @Will 2015-11-05 23:06:54

@SamKing where did you get your recursive solution from?

## @Will 2015-11-05 23:29:53

[edit: nvm I think I found it] jeffe.cs.illinois.edu/teaching/algorithms/notes/…

## @Alperen 2017-10-09 13:23:54

This is a very useful solution, but I need to note that I took

`TypeError: list indices must be integers or slices, not float`

error in dynamic solution code because of the line`mid = (high + low) / 2`

. I guess, it should be`mid = (high + low) // 2`

or`mid = int((high + low) / 2)`

## @Sam King 2017-10-09 17:29:23

All of the code is working python2 code. If you're running it in python3, you might have some issues.

## @Shashank Agarwal 2015-03-08 22:55:54

This is a Java implementation in O(n^2). I just did not use Binary Search to find the smallest element in S, which is >= than X. I just used a for loop. Using Binary Search would make the complexity at O(n logn)

## @fatih tekin 2015-05-14 18:20:24

here is java O(nlogn) implementation

## @bholagabbar 2015-04-16 15:56:21

Here's another O(n^2) JAVA implementation. No recursion/memoization to generate the actual subsequence. Just a string array that stores the actual LIS at every stage and an array to store the length of the LIS for each element. Pretty darn easy. Have a look:

Code in action: http://ideone.com/sBiOQx

## @lcn 2014-12-14 05:21:55

Here is a Scala implementation of the O(n^2) algorithm:

## @Barun Sharma 2014-04-13 19:57:01

This can be solved in O(n^2) using Dynamic Programming. Python code for the same would be like:-

For input:

`5 19 5 81 50 28 29 1 83 23`

output would be:

`[1, 2, 1, 3, 3, 3, 4, 1, 5, 3] 5`

The list_index of output list is the list_index of input list. The value at a given list_index in output list denotes the Longest increasing subsequence length for that list_index.

## @Iuri Covalisin 2013-11-13 00:54:34

Here are three steps of evaluating the problem from dynamic programming point of view:

If we take as an example sequence {0, 8, 2, 3, 7, 9}, at index:

Here's the working C++11 code:

## @Slothworks 2016-10-16 04:29:04

I think the recurrence definition should be maxLength(i) = 1 + max(maxLength(j)) for 0 < j < i and array[i] > array[j] rather than without the max().