title: Find buy/sell prices in array of stock values to maximize positive difference
body: <p>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...)</p>
  
  <p><b>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).</b></p>
  
  <p>To illustrate with an example, let's take the stock ticker of Company Z:</p>
  
  <pre><code>55.39 109.23 48.29 81.59 105.53 94.45 12.24
  </code></pre>
  
  <p>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.</p>
  
  <p>(in the above example, the ideal solution is to buy at <code>48.29</code> and sell at <code>105.53</code>)</p>
  
  <p>I came up with the naive solution easily enough with O(n<sup>2</sup>) complexity (implemented in java):</p>
  
  <pre><code>// 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&lt;Double&gt; 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 &lt; prices.size(); i++) {
      for (int j = i + 1; j &lt; prices.size(); j++) {
        double difference = prices.get(j).doubleValue() - 
                            prices.get(i).doubleValue();
  
        if (difference &gt; 0.0) {
          if (retval[BUY] &lt; 0 || difference &gt; prices.get(retval[SELL]).doubleValue() - 
                                              prices.get(retval[BUY]).doubleValue()) {
            retval[BUY] = i;
            retval[SELL] = j;
          }
        }
      }
    }
    return (retval[BUY] &gt; 0 ? retval : null);
  }
  </code></pre>
  
  <p>Here's where I screwed up: there's a <b>linear time O(n) solution</b>, 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!</p>
  
  <p><b>Edit</b></p>
  
  <p>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. :(</p>