Branden Olson CSCI 3104 April 14, 2013
Longest Increasing Subsequence
Suppose you are given some sequence of distinct whole numbers written in an arbitrary order, and your task is to find the length of its longest increasing subsequence. For completeness, imagine that you should also identify one such subsequence, as there may be more than one. Could we find an appropriate algorithm? In fact, there are several algorithms to accomplish this task, and here we will focus on one of the quickest. This algorithm relies on a sorting algorithm called patience sorting, which treats the elements like cards in a deck and arranges them as follows: First, put the first card (element) in its own pile. Each new card may be placed either on an existing pile whose top card has a value higher than the new card's value, thus increasing the number of cards in that pile, or to the right of all of the existing piles, forming a new pile. We are done when there are no more cards left, i.e., we have sorted each element in the sequence. Interestingly, the number of piles is the length of the longest subsequence. (Why?) In order to produce one subsequence of maximum length, we do the following: For each card we lay down, create a back-pointer to the top card in the previous pile. When we are finished, we follow the backpointers from the top card in the last pile to recover a decreasing subsequence of the longest length; its reverse is an answer to the longest increasing subsequence algorithm. To fix ideas, suppose you have a sequence Here we demonstrate how this algorithm works: Step 1: Step 2: Step 3: Step 4: Step 5: Step 6: Step 7:
Each represents the pile. Notice that when we lay 7, the final card, we create a back-pointer to 6 in the previous pile, which, when laid down, was given a back-pointer to 4 from its previous pile, which was given a backpointer to 3 from the very first pile. Thus, concatenating these numbers in reverse, we have
which can easily be verified as the longest increasing subsequence in our original . Notice that this will only work if each pointer remains unaltered after its initial assignment. Here is accompanying pseudocode for the algorithm: ALGORITHM LongestIncreasingSubsequence(A*1, , n+) // Finds the length of the subsequence of the given array of maximum length, // along with one such subsequence // Input: Array A*1, , n+ of distinct elements (A.size > 0) // Output: Array B*1, , m+ of the longest increasing subsequence of A Initialize list of piles (array or list) Add A[0] to Heap #1 for i := 1, , n for each existing heap if A[i] < top card of heap add A[i] to heap A[i].previous := top card of previous heap else create new heap; add A[i] to new heap pointer := top card of last pile B[0] := pointer j := 1 while pointer != null pointer := pointer.previous B[j] := pointer j := j + 1 reverse the order of the elements in B return B What is the time and space complexity of this algorithm? Observe that the innermost loop is executed for each element in the original list, and for each current pile. Thus, in the worst case, a new pile is created with each iteration, and so the number of comparisons is estimated as follows:
Thus, the algorithm carries a cubic worst-case time complexity. This also assumes that creating a new pile runs in constant time. In the best case, we only have one pile the entire algorithm, and so the number of comparisons would roughly be giving a much better result of linear time complexity.
The space complexity is not too difficult to analyze, but largely depends on the data structure used for implementation. The given array and output array both require space , and the piles should never require more than linear space. Thus it is safe to say that the space complexity of this algorithm is .
