O(nlgn)-time algorithm to find the LIS

In the spirit of dynamic programming, we first consider what information we would need from previous problems to solve for a longest increasing sub-sequence in A[n]. There are two cases:

Case 1. The length of the LIS(s) of A[n] is equal to the length of the LIS(s) of A[n-1].
        This will occur when for all A[k], where A[k] is the last element in a longest increasing sub-sequence 
        of A[n-1], A[n] <= A[k].

Case 2. The length of the LIS(s) of A[n] is equal to 1 + the length of the LIS(s) of A[n-1].
        This will occur when A[n] > than some A[k], where A[k] is the last element in a longest increasing 
        sub-sequence of A[n-1].

Clearly Case (2) is desired, since we are increasing the length of the LIS. So what differentiates Cases (1) and (2)? Well, note that to be in Case (1), A[n] must be less than ALL of some elements A[k], whereas to be in Case (2), A[n] must simply be greater than ONE instance of A[k]. To maximize the chances of the latter case, then, we would want to keep track of the minimum A[k] that yields a longest sub-sequence of some number of elements.

To get the longest sub-sequence itself, we must also have a way to keep track of which elements are part of our current chain, since we are changing values. We do this by maintaining a new array that holds the previous element in the longest chain starting with the element that we’re using. This will be clearer in an example below.

Summary:

  1. In increasing indexing order though the array, compare a new element to the last element in the current LIS. If the new element is larger, we attach to the LIS. Update the array for previous values here. This runs in O(n) time.

  2. If the new element is not larger, we find the smallest element in the LIS sequence that is larger than our value and replace it with our current value. We can find this element using binary search, since the values index by I[ ] are in ascending order. This runs in O(log(n)) time.

  3. Trace back through the previous-index-array to recover the actual sub-sequence. This runs in O(n) time.

Example:

A = [2, 4, 1, 8, 9, 5, 6, 7]

I[k] holds the index of the last element in some increasing sub-sequence(not longest increasing sub-sequence) of k values. And A[I[0]] < A[I[1]] < … < A[I[len(I) - 1]].

P[k] holds the index of the previous value in the longest increasing sub-sequence of k values.

2: I[ ] = {0},                  P[ ] = {}               LIS is {2}
4: I[ ] = {0, 1},               P[ ] = {0}              LIS is {2, 4}
1: I[ ] = {2, 1},               P[ ] = {0}              LIS is {2, 4}
8: I[ ] = {2, 1, 3},            P[ ] = {0, 1}           LIS is {2, 4, 8}
9: I[ ] = {2, 1, 3, 4},         P[ ] = {0, 1, 3}        LIS is {2, 4, 8, 9}
5: I[ ] = {2, 1, 5, 4},         P[ ] = {0, 1, 3}        LIS is {2, 4, 8, 9}
6: I[ ] = {2, 1, 5, 6}          P[ ] = {0, 1, 5}        LIS is {2, 4, 5, 6}
7: I[ ] = {3, 2, 5, 6, 7}       P[ ] = {0, 1, 5, 6}     LIS is {2, 4, 5, 6, 7}

Pseudo Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//Input: An array A 
//Output: The Longest Increasing Sub-sequence of A

LONGEST-INCREASING-SUBSEQUENCE(A)
   // let I[ ], P[ ] be new arrays; initialize I[0] = 0(the index of the first element in A[])
   // let a be the index of the last element in I[ ]
   a = 0
   for i = 1 to n - 1       // len(A) = n
      if A[i] > A[I[a]]     // New element greater than our current LIS's largest
         a = a+1            // Grow I[ ]
         I[a] = i           // Append new element's index to I[ ]
         P[a-1] = I[a-1]    // Save the index of previous value of new largest element of LIS
      else
         do binary search in I[1... a] for j such that: A[I[j]] is the smallest element in all A[I[j]], j=0,1,...len(I[]) and A[I[j]] > A[i]  
         I[j] = i           // Update the best LIS of length j to be this smaller element
         if j == a          // Check if j was the last element in LIS
            P[b] = I[a-1]   // Update previous value; would have changed in a former loop iteration
   
   // let LIS[a] be a new array
   LIS[a] = A[I[a]]         // Last element in LIS is indexed by last element in I[ ]
   for i = a - 1 down to 1  // Go through and set LIS array to the proper values
      LIS[i] = A[P[b]]
   return LIS