  In this paper we examine problems motivated by on-line financial problems and
stochastic games. In particular, we consider a sequence of entirely arbitrary
distinct values arriving in random order, and must devise strategies for
selecting low values followed by high values in such a way as to maximize the
expected gain in rank from low values to high values.
  First, we consider a scenario in which only one low value and one high value
may be selected. We give an optimal on-line algorithm for this scenario, and
analyze it to show that, surprisingly, the expected gain is n-O(1), and so
differs from the best possible off-line gain by only a constant additive term
(which is, in fact, fairly small -- at most 15).
  In a second scenario, we allow multiple nonoverlapping low/high selections,
where the total gain for our algorithm is the sum of the individual pair gains.
We also give an optimal on-line algorithm for this problem, where the expected
gain is n^2/8-\Theta(n\log n). An analysis shows that the optimal expected
off-line gain is n^2/6+\Theta(1), so the performance of our on-line algorithm
is within a factor of 3/4 of the best off-line strategy.
