I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming.
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]
.
int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;
for (int i = 1; i < N; i++)
{
DP[i] = 1;
prev[i] = -1;
for (int j = i - 1; j >= 0; j--)
if (DP[j] + 1 > DP[i] && array[j] < array[i])
{
DP[i] = DP[j] + 1;
prev[i] = j;
}
if (DP[i] > maxLength)
{
bestEnd = i;
maxLength = DP[i];
}
}
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.
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:
0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 9} - New largest LIS
8. S = {1, 2, 4, 5} - Changed 9 to 5
9. S = {1, 2, 4, 5, 8} - New largest LIS
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:
input[S[lastElementOfS]],
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................
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]
.