Find buy/sell prices in array of stock values to maximize positive difference

Question

Got this question in an interview today, and its optimized solution stopped me cold (which blows, because I really wanted to work for this company...)

Given a single array of real values, each of which represents the stock value of a company after an arbitrary period of time, find the best buy price and its corresponding best sell price (buy low, sell high).

To illustrate with an example, let's take the stock ticker of Company Z:

55.39 109.23 48.29 81.59 105.53 94.45 12.24

Important to note is the fact that the array is "sorted" temporally - i.e. as time passes, values are appended to the right end of the array. Thus, our buy value will be (has to be) to the left of our sell value.

(in the above example, the ideal solution is to buy at 48.29 and sell at 105.53)

I came up with the naive solution easily enough with O(n²) complexity (implemented in java):

// returns a 2-element array: first element is the index in the argument array
// of the best buying price, and the second element is the index of the best
// selling price which, collectively, maximize the trading return
//
// if there is no favorable trading (e.g. prices monotonically fall), null is returned
public int[] maximizeReturn(ArrayList<Double> prices) {
  int [] retval = new int[2];
  int BUY = 0, SELL = 1;
  retval[BUY] = retval[SELL] = -1; // indices of buy and sell prices, respectively

  for (int i = 0; i < prices.size(); i++) {
    for (int j = i + 1; j < prices.size(); j++) {
      double difference = prices.get(j).doubleValue() - 
                          prices.get(i).doubleValue();

      if (difference > 0.0) {
        if (retval[BUY] < 0 || difference > prices.get(retval[SELL]).doubleValue() - 
                                            prices.get(retval[BUY]).doubleValue()) {
          retval[BUY] = i;
          retval[SELL] = j;
        }
      }
    }
  }
  return (retval[BUY] > 0 ? retval : null);
}

Here's where I screwed up: there's a linear time O(n) solution, and I completely bombed in trying to figure it out (yeah, I know, FAIL). Does anyone know how to implement the linear time solution? (any language you're comfortable with) Thanks!

Edit

I suppose, for anyone interested, I just received word today that I didn't get the job for which I interviewed where they asked me this question. :(

Answer 1

In C#:

static void Main(string[] args)
{
    double[] values = new double[7]{55.39, 109.23, 48.29, 81.59, 105.53, 94.45, 12.24};

    double max = double.MinValue, maxDiff = double.MinValue, diff = 0;

    for (int i = 1; i < values.Length; i++)
    {
        if (values[i] > values[i - 1])
        {
            //trending upward, append to existing differential
            diff += values[i] - values[i - 1];
        }
        else
        {
            //trending downward, reset the diff
            diff = 0;
        }

        if (diff > maxDiff)
        {
            maxDiff = diff;
            max = values[i];
        }
    }

    Console.WriteLine("Buy at {0}; Sell at {1}", max - maxDiff, max);
}

EDIT: New algo based on @Joe's failing test case -- Nice Catch BTW! It's also the same answer as @Doug T's now...

static void Main(string[] args)
{
    double[] values = new double[8] { 55.39, 109.23, 48.29, 81.59, 81.58, 105.53, 94.45, 12.24 };

    double max = double.MinValue, maxDiff = double.MinValue, diff = 0;
    double bottom = values[0];

    for (int i = 1; i < values.Length; i++)
    {
        diff += values[i] - values[i - 1];

        if (diff > maxDiff)
        {
            maxDiff = diff;
            max = values[i];
        }

        if (values[i] < bottom)
        {
            bottom = values[i];
            diff = 0;
        }
    }

    Console.WriteLine("Buy at {0}; Sell at {1}", max - maxDiff, max);
}