The minimal longest ascending subsequence algorithm

Suppose that we are given a sequence of distinct integers, X = {x[0], …, x[N-]}. A subsequence S = {s0 … sm} is said to be an ascending subsequence if s0 < … < sm.

Example:
Let X = {0,9,3,2,5,6,8,1,4,7}
Let S = {0,2,4,7}

Ascending subsequences with the same length can be compared lexicographically, proceeding from the last elements and working forward. For example, consider the following three subsequences of X:

S1 = {0,2,4,7}
S2 = {0,3,5,6}
S3 = {0,2,5,6}

Then S3 < S2 < S1. S1 is greater than S2 and S3 because 7>6; S2>S3 because 3>2. The lexicographic comparison establishes an order on ascending subsequences with the same length. It follows that, for any given subsequence length, there is a minimal ascending subsequence which is less than all other subsequences with the same same length.

Obviously there is some m such that no ascending subsequence has a length greater than m. An ascending subsequence of length m is a longest ascending subsequence. It follows that there is exactly one minimal longest ascending subsequence, the MLAS.

The MLAS algorithm determines the minimal longest ascending subsequence. As a collateral benefit it determines the minimal ascending sequences for all lengths 1 … m.

The MLAS algorithm is a greedy algorithm. The general plan is: Suppose that we have determined the minimal ascending subsequences for the subsequence X(n) = {x(0) … x(n-1)} of X. We use these and the value of x(n) to determine the minimal ascending subsequenes for the extended subsequence {x(0) … x(n)}.

Let M(m,n) be the minimal ascending subsequence of length m in the the sequence X(n) = {x[0]…x[n-1]} and let T(m,n) be the terminal element of M(m,n). It follows immediately that

T[1,n] < T[2,n] < … < T[max,n] i.e., the terminal elements are ordered. This follows by a reductio ad absurdum. If there were an i such that

T[i,n] >= T[i+1,n]

then the first i elements of M(i+1,n) would constitute an ascending subsequence lexicographically preceding M(i,n).

Now consider extending X(n) to X(n+1) by adjoining x[n].
Either x[n] < T[1,n], i.e., x[n] is less than the first terminal,
or x[n] > T[max,n], i.e., x[n] is greater than the last terminal
or else there is an i such that T[i,n] < x[n] < T[i+1,n]

In the first case, x[n] < T[1,n], we set M(1,n+1) = {x[n]},
i.e., M(1,n+1) consists of the single element, x[n].

In the second case, x[n] > T[max,n], we set M(max+1,n+1) = {M(max,n), x[n]},
i.e., we append x[n] to M(max,n) to get M(max+1,n+1).
Note that x[n] becomes a new largest terminal.

Finally, if there is an i such that T[i,n] < x[n] < T[i+1,n],
then we set M(i+1,n+1) = {M(i,n),x[n]},
i.e., we append x[n] to M(i,n) to get M(i+1,n+1).

In all of these cases the subsequences for n+1 are the same as those for n except for the one containing x[n]. As an illustion suppose that the sequence is {100,300,50,200}. Then the M sequences are:

n=1: M(1,1) = {100}
n=2: M(1,2) = {100}, M(2,2) = {100, 300}
n=3: M(1,3) = {50}, M(2,3) = {100,300}
n=4: M(1,4) = {50}, M(2,4) = {50,200}

We now consider the issue of data structures appropriate for implementing the algorithm. Clearly we do not want to store the full content of the intermediate ascending subsequences; the storage required would be O(N**2). However this is not necessary. Each element x[i] either has no predecessor (if it is a minimal ascending subsequence of length 1) or it has exactly one predecessor assigned to it, the assignment being made when the iteration passes through x[i]. Hence it suffices to have an array of length N to represent the back pointers (it is more convenient to have this array hold the indices of the predecessors. It is also necessary to have an array of length N to hold the terminal elements T (it will be more convenient to use this array to hold the indices of the terminal elements.) The extraction of the longest ascending subsequence at the end can be done by first finding the last element of the longest ascending sequence in the terminals array and then following predecessors backwards.

The cost of this algorithm depends on the efficiency of the search. If the length of the longest ascending subsequence is O(N) and we use a binary search the algorithm cost is O(N*logN). The conditions are suitable, however, for a secant search; given a secant search the cost is O(N*logN**.618).

Pseudocode For The MLAS Algorithm

Note: The pseudocode here uses a binary search.

   begin public interface procedure min_las(seq,las,n,n_as)
      dcl seq;  typeof numeric[]; callby address   // input sequence
      dcl las;  typeof numeric[]; callby address   // output sequence
      dcl n;    typeof in;        callby value     // length of input
      dcl n_as; typeof int;       callby address   // length of output
      assert n .gt. 0
   end public interface
   begin procedure min_las
      dcl terminals; typeof int[1...n]    // array of terminals
      dcl backptrs;  typeof int[0...n-1]  // array of back pointers
      dcl low;       typeof int           // low bound in bin search
      dcl high;      typeof int           // high bound in bin search
      dcl mid;       typeof int           // mid point of search interval
      dcl i;         typeof int           // index for loop thru seq[]
      dcl temp;      typeof int           // temp used for las build
      terminals[1] = 0
      backptrs[0]  = -1
      n_as         = 1
      begin loop i = 1...n-1
         low  = 1
         high = n_as
         begin loop while (low .le. high)
            mid = (low+high)/2
            if (seq[i] .le. seq[terminals[mid]) high = mid-1
            else                                low  = mid+1
         end loop
         terminals[low] = i
         if (low .le. 1) backptrs[i] = -1
         else            backptrs[i] = terminals[low-1]
         if (low .gt. n_as) n_as += 1
      end loop
      las[n_as-1] = seq[terminals[n_as]]
      temp        = terminals[n_as]
      begin loop i = n_as-2...0
         temp   = backptrs[temp]
         las[i] = seq[temp] 
      end loop
   end procedure min_las     

---

This page was created February 1, 2001.
This page was last updated December 26, 2006.