How to determine the longest increasing subsequence using dynamic programming?

algorithm, computer-science, dynamic-programming, lis, memoization

Solution

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.

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 essentially 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 an element with index `i` in the `LIS` ending at the 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]`.

Problem

Original source