Here's an approach that is considerably faster when the input is a random permutation.  For a list of length 100 it is 30x faster.  It only computes the length, not the actual sequence:

longestIncreasingSequenceLength2 := proc(L::list)
local n,i,j,G;
uses GraphTheory;
    n := nops(L);
    G := Digraph(n
                 , {seq(seq(`if`(L[i]<L[j]
                                 , [i,j]
                                 , NULL
                                )
                            , j = i+1..n)
                        , i = 1..n-1)}
                );
    LengthDAG(G);
end proc:

LengthDAG := proc(G)
local len, sources, v;
uses GraphTheory;
    len := proc(v)
    option cache;
    local j,dep;
    uses GraphTheory;
        dep := Departures(G,v);
        if dep = [] then
            1
        else
            1 + max(seq(procname(j), j in dep))
        end if;
    end proc;
    sources := select(v -> Arrivals(G,v)=[], Vertices(G));
    max(seq(len(v), v in sources));
end proc:

Here are the corresponding procedures for returning a longest sequence.  By using attributes, LongestPathOfDAG is practically identical to LengthDAG.

longestIncreasingSequence := proc(L::list)
local n,i,j,G;
uses GraphTheory;
    n := nops(L);
    G := Digraph(n
                 , {seq(seq(`if`(L[i]<L[j]
                                 , [i,j]
                                 , NULL
                                )
                            , j = i+1..n)
                        , i = 1..n-1)}
                );
    map(op,LongestPathOfDAG(G),L);
end proc:

LongestPathOfDAG := proc(G)
local len, sources, v;
uses GraphTheory;
    len := proc(v)
    option cache;
    local j,dep,longest;
    uses GraphTheory;
        dep := Departures(G,v);
        if dep = [] then
            setattribute(Float(1),v);
        else
            longest := max(seq(procname(j), j in dep));
            setattribute(1 + longest, v, attributes(longest));
        end if;
    end proc;
    sources := select(v -> Arrivals(G,v)=[], Vertices(G));
    [attributes(max(seq(len(v), v in sources)))];
end proc:

Thanks for working this out. I was thinking about this on my daily walk and realized that using cliques had to be overkill (i.e. grossly inefficient). Yours is a nice solution.

Thanks for working this out. I was thinking about this on my daily walk and realized that using cliques had to be overkill (i.e. grossly inefficient). Yours is a nice solution.

But that implies the minimum value is 2.

But that implies the minimum value is 2.

There is a slight inefficiency in my code. The range for j should be j = i+1..n, not j = i..n.

There is a slight inefficiency in my code. The range for j should be j = i+1..n, not j = i..n.

Hmm.

longestIncreasingLength([1,2,3,4]);

                                                           3

longestIncreasingLength([1,4,2]);

                                                           1

Hmm.

longestIncreasingLength([1,2,3,4]);

                                                           3

longestIncreasingLength([1,4,2]);

                                                           1

Yeah, I wondered about that after posting.  Thanks for the clarification.

Yeah, I wondered about that after posting.  Thanks for the clarification.

In addition to a sourceforge account, we need a means for building Maple libraries from the the source.  Presumably a small set of scripts that will work with both Linux and Windows [the latter is the pain].  Can we assume that any Windows contributors have cygwin installed? This assumes that the source code consists of ascii files, not Maple worksheets.

Using a custom boolean operator is, as you say, the easiest approach.  However, it isn't necessarily the fastest or more efficient technique.  For many applications than may not matter.   If speed is important, you might look at an earlier blog entry that was motivated by John's post.

That doesn't work.  It only sorts on the first element of a list.  Try it with, say,

L := [[1,2],[1,1]];

Seems like the hard part is setting up the logistics of a collaboration. Has anyone here had experience running or contributing to a SourceForge project?  How does that work?  Is there a better approach?  I'm curious; what, if any, source code control people use for personal projects.  I used to use cvs, but have recently switched to git.