How to determine the longest increasing subsequence using dynamic programming?

Question

Let's say I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming. This is simply out of practice, reviewing my old notes from my algorithms course, and I don't seem to understand how this works.

Thanks

Answer 1

OK, I will describe the simplest solution which is O(N^2), where N is the size of the set. There also exists a O(N log N) solution. 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.