not quite n-log-n, but perhaps a useful idea

[Henry Cejtin]

I  thought that I actually had a proof of n log n, but it wasn't quite right,
but it may give some heuristic input.

The idea is that you divide the input in half.  Then you optimally solve  the
left  and  right  half.  Now the only way you can do better than just putting
these two solutions next to each other is by having things open in  the  left
which close in the right.

I  thought that this would be a bounded amount of possibilities, and then you
could just keep track of all of them, but it isn't since the nesting depth at
the  midpoint of an optimal solution of the whole thing could be O(size), but
still I think that this may be a good approach.  If you had  any  fixed  data
from the left and right half and it took a constant amount of work to produce
that data for the whole thing, then the whole algorithm would be n log n.