Optimal Sequential Selection of a Monotone Sequence From a Random Sample

The length of the longest monotone increasing subsequence of a random sample of size n is known to have expected value asymptotic to 2n1/2. We prove that it is possible to make sequential choices which give an increasing subsequence of expected length asymptotic to (2n)1/2. Moreover, this rate of increase is proved to be asymptotically best possible