I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming.
相关问题
- Finding k smallest elements in a min heap - worst-
- binary search tree path list
- High cost encryption but less cost decryption
- How to get a fixed number of evenly spaced points
- Space complexity of validation of a binary search
相关文章
- What are the problems associated to Best First Sea
- Coin change DP solution to keep track of coins
- Algorithm for partially filling a polygonal mesh
- Robust polygon normal calculation
- Algorithm for maximizing coverage of rectangular a
- How to measure complexity of a string?
- Select unique/deduplication in SSE/AVX
- How to smooth the blocks of a 3D voxel world?
The following C++ implementation includes also some code that builds the actual longest increasing subsequence using an array called
prev
.Implementation with no stack just reverse the vector
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:
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 .
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 indexi
. To computeDP[i]
we look at all indicesj < i
and check both ifDP[j] + 1 > DP[i]
andarray[j] < array[i]
(we want it to be increasing). If this is true we can update the current optimum forDP[i]
. To find the global optimum for the array you can take the maximum value fromDP[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 frombestEnd
in a loop usingprev[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 lengthpos
. Now iterate through every integerX
of the input set and do the following:If
X
> last element inS
, then appendX
to the end ofS
. This essentialy means we have found a new largestLIS
.Otherwise find the smallest element in
S
, which is>=
thanX
, and change it toX
. BecauseS
is sorted at any time, the element can be found using binary search inlog(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. Letparent[i]
be the predecessor of element with indexi
in theLIS
ending at element with indexi
.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 inS
, thenparent[indexX] = indexLastElement
. This means the parent of the newest element is the last element. We just prependX
to the end ofS
.Otherwise find the index of the smallest element in
S
, which is>=
thanX
, and change it toX
. Hereparent[indexX] = S[index - 1]
.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
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.