title: Buy and sell stock in a day
body: <p>I was asked this problem in a interview:</p>
  
  <p><a href="http://www.leetcode.com/2010/11/best-time-to-buy-and-sell-stock.html" rel="nofollow">Best Time to Buy and Sell Stock</a></p>
  
  <p>Say you have an array for which the ith element is the price of a given stock on day i.
  If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell. I was able to give an O(n) algorithm.</p>
  
  <p>While the interviewer asked me a followed on question, what is the case with "buy one, sell one", and then "buy one, sell one", which means there are two trades in one day, maximize the profit. I was able to give an O(n^2) algorithm. But the interviewer said it can be improved. Is there a O(n) algorithm? </p>
  
  <p>The interviewer said that you can not buy two share at the same time. You must buy one sell it, and then buy one at another time, then sell it.</p>